折半查找法的两种实现形式.docx

折半查找法的两种实现 折半查找法： 在有序表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现： 待查找数据值与中间元素值正好相等，则放回中间元素值的索引。 待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），知道找到相等的值。 待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），知道找到相等的值 如果最后找不到相等的值，则返回错误提示信息。 按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为 log2(n+1)-1 //Data为要查找的数组，x为待查找数据值，beg为查找范围起始，last为查找范围终止 //非递归法 int BiSearch(int data[], const int x, int beg, int last) { int mid;//中间位置 if (beg last) { return -1; } while(beg = last) { mid = (beg + last) / 2; if (x == data[mid] ) { return mid; } else if (data[mid] x) { beg = mid + 1; } else if (data[mid] x) { last = mid - 1; } } return -1; } //递归法 int IterBiSearch(int data[], const int x, int beg, int last) { int mid = -1; mid = (beg + last) / 2; if (x == data[mid]) { return mid; } else if (x data[mid]) { return IterBiSearch(data, x, beg, mid - 1); } else if (x data[mid]) { return IterBiSearch(data, x, mid + 1, last); } return -1; } //主函数 int _tmain(int argc, _TCHAR* argv[]) { int data1[60] = {0}; int no2search = 45; cout The array is : endl; int siz = sizeof(data1)/sizeof(int); for (int i = 0; i siz; i++) { data1[i] = i; cout data1[i] ; } cout endl; int index = -1; //index = BiSearch(data1, no2search, 0, siz); index = IterBiSearch(data1, no2search, 0, siz); cout Index of no2search is index endl; getchar(); return 0; }