●顺序查找
顺序查找比较简单,就是顺序遍历我们所要查找的内容,判断并找出相应的目标数。比较简单,在这里不用图形说明程序实现具体情况。当面临大量数据时,顺序查找的效率非常低,时间复杂度大,所以会采用其他方法进行查找。
#include<iostream>
using namespace std;
#define size 20
class shunxu {
public:
void searchfun()
{
for (int i = 0; i < size; i++)
{
if (arr[i] == n)
place = i;
}
}
int arr[size];
int n;
int place;
};
void text()
{
shunxu sx;
cout << "输入顺序查找的内容:";
for (int i = 0; i < size; i++)
{
cin >> sx.arr[i];
}
cout << "输入要查找的目标:";
cin >> sx.n;
sx.searchfun();
cout << "所查找目标的位置:" << sx.place << endl;
}
int main()
{
text();
}
●折半查找
在下面我们从十个数中查找目标数,用折半查找法进行查找(在这里不进行排序,只进行折半查找),如下图所示。
第一次,low=0、high=9 => mid=4,进行判断arr[mid]<n,则定位到后半段,low=mid+1;
第二次,low=5、high=9 => mid=7,进行判断arr[mid]>n,则定位到前半段,high=mid-1;
第三次,low=5、high=6 => mid=5,进行判断arr[mid]<n,则定位到后半段,low=mid+1;
第四次,low=6、high=6 => mid=6,进行判断arr[mid]=n,找到目标值的位置,place=6;
当面临大量数据时,我们先将这些数据进行排序,再用折半查找法进行查找。这样可以极大的提高查找效率,降低时间复杂度从而快速的寻找到目标数。
#include<iostream>
using namespace std;
#define size 20
class halfsearch {
public:
void bullesort_1(); //对随机生成的数进行排序,随机找一种排序算法即可,这里用冒泡这种简单排序法
int halfsearch_1() //折半查找
{
int low=0, mid, high=size-1;
while (low<=high)
{
mid = (low + high) / 2; //折半
if (arr[mid] == n)
return place = mid;
else if (arr[mid] > n) //目标数在前一半里
high = mid - 1;
else //目标数在后一半里
low = mid + 1;
}
return place = 0;
}
void showplace()
{
if (place == 0)
cout << "没有找到" << endl;
else
cout << "找到目标数且位置为:" << place+1 << endl;
}
int arr[size];
int n;
int place;
};
void halfsearch::bullesort_1() //冒泡排序法
{
int temp;
for (int i = 0; i < size-1; i++)
{
for(int j=size-1;j>i;j--)
{
if (this->arr[j ] < this->arr[i])
{
temp = this->arr[j ];
this->arr[j ] = this->arr[i];
this->arr[i] = temp;
}
}
}
}
void text()
{
halfsearch hs;
srand(time(NULL));
for(int i=0;i<size;i++)
{
hs.arr[i] = rand() / 1000 + 100; //生成100~200的随机数
}
hs.bullesort_1(); //先进行排序,后进行折半查找
cout << "随机生成的数排序后如下:" << endl;
for (int j = 0; j < size; j++)
{
cout << hs.arr[j] << " ";
}
cout<<endl;
cout << "输入要查找的数:";
cin >> hs.n; //输入要查找的目标数
hs.halfsearch_1(); //进行折半查找
hs.showplace(); //输出查找到的位置
}
int main()
{
text();
}
文章出处登录后可见!
已经登录?立即刷新