折半查找

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(log₂N)

. 更多信息，请查看 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的比较次数为（）。

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比较