●顺序查找
顺序查找比较简单，就是顺序遍历我们所要查找的内容，判断并找出相应的目标数。比较简单，在这里不用图形说明程序实现具体情况。当面临大量数据时，顺序查找的效率非常低，时间复杂度大，所以会采用其他方法进行查找。
#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(); }
