1、折半查找又称为二分查找，是一种效率较高的查找方法。
2、折半查找的前提条件：
查找表中的所有记录是按关键字有序(升序或降序) 。
查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围(每次将待查记录所在区间缩小一半)，直到找到或找不到记录为止。
3、查找的算法可以简述为以下：
用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。
⑴ 取中间位置Mid：Mid=(Low+High)/2；
⑵ 比较中间位置记录的关键字与给定的K值：
① 相等： 查找成功；
② 大于：待查记录在区间的前半段，修改上界指针：High=Mid-1，转⑴ ；
③ 小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转⑴ ；
直到越界(Low>High)，查找失败。
4、查找的算法分析
① 查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示：
◆ 根结点就是第一次进行比较的中间位置的记录；
◆ 排在中间位置前面的作为左子树的结点；
◆ 排在中间位置后面的作为右子树的结点；
对各子树来说都是相同的。这样所得到的二叉树称为判定树(Decision Tree)。
② 将二叉判定树的第㏒2n+1层上的结点补齐就成为一棵满二叉树，深度不变，h= ㏒2。
③ 由满二叉树性质知，第i 层上的结点数为2i-1(i≤h) ，设表中每个记录的查找概率相等，即Pi=1/n，查找成功时的平均查找
长度ASL：
当n很大 (n>50)时， ASL≈ ㏒2(n+1)-1
5、折半查找的代码实现
#include <iostream>using namespace std;//递归折半
bool fold_findo(int m, int arr[], int low, int high)
{bool result = false;if(low <= high){int mid = (low + high) / 2;if(m == arr[mid]){return true;}else if(m < arr[mid]){result = fold_findo(m, arr, low, mid - 1);}else{result = fold_findo(m, arr, mid + 1, high);}return result;}else{return false;}
}//迭代折半
bool fold_finds(int m, int arr[], int low, int high)
{int mid;while(low <= high){mid = (low + high) / 2;if(m == arr[mid]){return true;}else if(m < arr[mid]){high = mid - 1;}else{low = mid + 1;}}return false;
}int main()
{int m; //需要查找的元素int arr[] = {-10, -5, 0, 1, 2, 4, 6, 9, 12, 18, 20, 26};int len = sizeof(arr) / sizeof(int);cin >> m;bool result = fold_finds(m, arr, 0, len - 1);if(result == true){cout << "Find yes!" << endl;}else{cout << "No find!" << endl;}return 0;
}
