折半查找

Binary Search
. 也叫二分查找
过程 Procedure
. 将表看作一个查找区间，用low、high，mid = (low + high)/2 来标识查找区间的下界、上界和中间位置
. mid是整除的结果；如果给定值和mid对应的值相等，查找成功
. 如果给定值小于中间记录值，则在前半段继续查找，high = mid - 1，low不变
. 如果给定值大于中间记录值，则在后半段继续查找，low = mid + 1，high不变
. 如果比较到最后，low > high ，查找结束
. 查找范围每次都缩小一半，所以查找效率高
查找过程
0 ... ... (0+n)/2 ... ... n
data ... ... data ... ... data
↑ ↑ ↑
low mid high
伪代码 Pseudo Code
. 封装为函数：int binarySearch(int low,int high,int key)
#include <stdio.h>
int main () {
    int a[] = {0, 5, 13, 19, 22, 41, 55, 68, 72, 81, 98};
    int low = 0, high, mid, index = -1;
    high = sizeof(a)/sizeof(a[0]);
    int target = 12;
    while(low <= high){
        mid = (low + high)/2;
        if(a[mid] == target){
            index = mid;
            break;
        }else if(a[mid] < target){
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }

    if(index == -1){
        printf("Not Found\n");
    }else{
        printf("Found at %d\n",index);
    }

    return 0;
}
性能分析 Analysis
. 优点：查找效率高，特别适合大数据量
. 缺点：表必须是顺序存储的有序表
. 不适用于数据元素经常变化的表
. 时间复杂度 O(log2N)
. 更多信息，请查看 Binary Sort、懒猫老师
查找21的过程
二分查找
0 1 2 3 4 5 6 7 8 9 10
5 13 19 21 37 56 64 75 80 88 92
第一次查找：low = 0, high = 10, mid = (low + high)/2 = 5, 对应的数据为56 > 21, 说明21在前面一半
第二次查找：low = 0, high = 4, mid = (low + high)/2 = 2, 对应的数据为19 < 21, 说明21在后面一半
第三次查找：low = 3, high = 4, mid = (low + high)/2 = 3, 对应的数据为21 = 21, 查找成功
查找21的过程
第1次查找：
low = 0；high = 10
mid = (low + high)/2 = (0 + 10)/2 = 5
51 > 21，目标在前半段，∴ low = 0，high = mid – 1 = 4
第1次查找
0 1 2 3 4 5 6 7 8 9 10
6 10 20 21 49 51 69 79 82 88 94
low mid high
第2次查找：
low = 0；high = 4
mid = (low + high)/2 = (0 + 4)/2 = 2
20< 21，目标在后半段，∴ low=mid + 1=3，high=4
第2次查找
0 1 2 3 4 5 6 7 8 9 10
6 10 20 21 49 51 69 79 82 88 94
low mid high
第3次查找：
low = 3；high = 4
mid = (low + high)/2 = (3 + 4)/2 = 3
21== 21，查找结束
第3次查找
0 1 2 3 4 5 6 7 8 9 10
6 10 20 21 49 51 69 79 82 88 94
low|mid high
从0，5，13，19，22，41，55，68，72，81，98中查找68的比较次数为（ ）。
2
3
4
5
4次
从0，5，13，19，22，41，55，68，72，81，98中查找12的比较关键字分别是（ ）。
41，13，0，5
采用折半查找法对长度为12的有序表进行查找，在等概率情况下查找成功所需的平均比较次数为（ ）。
35/12
37/12
39/12
43/12
37/12；[构建完全二叉树]
1次查找成功：5
2次查找成功：2、8
3次查找成功：0、3、6、10
3次查找成功：1、4、7、9、11
合计 = 1 + 2*2 + 3*4 + 4*5 = 37
平均 = 37/12
给定折半查找有序表(4, 6, 10, 12, 20, 30, 50, 70, 88, 100, 120)。若查找表中元素58，则算法将依次与表中哪些元素比较大小才以失败结束？
0 1 2 3 4 5 6 7 8 9 10
4 6 10 12 20 30 50 70 88 100 120
第1次 low=0, high=10, mid=(low+high)/2=5, loc(5)=30<58, 58应在后半段
第2次 low=6, high=10, mid=(low+high)/2=8, loc(8)=88>58, 58应在前半段
第3次 low=6, high=7, mid=(low+high)/2=6, loc(6)=50<58, 58应在后半段
第4次 low=7, high=7, mid=(low+high)/2=7, loc(7)=70!=58, 58查找失败
结论：分别与：30、88、50、70比较
给定折半查找有序表如下表。若查找表中元素83，能否查找成功？如果成功，查找几次？分别与哪些记录比较？如果失败，分别与哪些记录比较？
0 1 2 3 4 5 6 7 8 9 10
6 10 20 21 49 51 69 79 82 88 94
第1次 low=0, high=10, mid=(low+high)/2=5, loc(5)=51<83, 83应在后半段
第2次 low=6, high=10, mid=(low+high)/2=8, loc(8)=82<83, 83应在后半段
第3次 low=9, high=10, mid=(low+high)/2=9, loc(9)=88>83, 83应在前半段，应该比9小；但是现在low已经是9了，出现异常，查找83失败
结论：分别与：51、82、88比较