实验目的 1.掌握顺序查找技术和拆半查找技术； 2. 掌握查找的算法实现
实验内容 1.产生n个随机整数用顺序查找的方法进行查找操作，要求输出要找关键字Key的过程。 1.给定n个有序整数用折半查找的方法进行查找操作，找关键字Key的过程。
分析 签到级难度，主要是考察折半查找思想的理解和应用。折半查找又称二分查找，需要先对数组 进行排序。为了不打乱原来的数组，可以将排序后的数组另外保存，为了求出查到的数在原来的 数组所在的下标，可以用一个指针数组来排序和查找，得到的指针减去原数组的地址即可得到 所求树的位置。时间复杂度log2(n)。
MyCode
#include<iostream> #include<stdio.h> #include<string.h> #include<string> #include<algorithm> #include<time.h> using namespace std; const int maxn = 20; //size of randon integer static int times = 1; //used by printInt() to control the integer output each line int randArray[maxn]; //the array saving randon integer //controal the format of print integer void printInt(int n){ string blank = " "; int len = 0; int tn = n; while (tn /= 10) len++; cout << n << blank.substr(0, 8-len); if (times % 10 == 0) cout << endl; times++; } void init(){ srand(time(0)); for (int i = 0; i < maxn; i++){ randArray[i] = rand() % 1000000; printInt(randArray[i]); } cout << "\n\n"; } //search a number by order void seqSearchTest(){ while (true){ cout << "Please input the number you want to search, input -1 to exit \n"; int input; int i = 0; cin >> input; if (input < 0) break; for (; i<maxn; i++){ cout << randArray[i]; if (randArray[i] == input) break; cout << "->"; } if (randArray[i] == input){ cout << "Find the integer you want, index is " << i << endl; } else{ cout << i << " is not in the array!" << endl; } } return; } //define the way of sort the pointer array bool cmp(int *&a, int *&b){ return *a > *b; } //binary search the array and get the index void binSearchTest(){ int *p[maxn]; for (int i = 0; i < maxn; i++){ p[i] = randArray + i; } sort(p, p + maxn, cmp); for (int i = 0; i < maxn; i++){ printInt(*p[i]); } while (true){ cout << "\nPlease input the number you want to search, input -1 to exit > "; int input; int i = 0; cin >> input; if (input < 0) break; int lr = 0; int rr = maxn - 1; int mid; cout << "================ begin to search =================\n"; while (lr <= rr){//## mid = (lr + rr) / 2; int midVal = *p[mid]; cout << midVal; if (midVal == input){ break; } cout << " -> "; if (midVal < input) rr = mid - 1; else lr = mid + 1; } cout << "\n===================================================\n"; if (*p[mid] == input){ cout << endl << "Find the integer you want , index is " << p[mid] - randArray << "\n\n"; } else{ cout << endl << "The integer you want not in the array ! \n\n"; } } return; } int main(){ init(); //seqSearchTest(); binSearchTest(); }备忘录 binSearchTest() 中的循环条件 lr <= rr 非常容易出错，以后的代码设计中一定要针对类似的与数组边界的细节多 加谨慎。
