缘由
今天浏览 何登成的技术博客 无意中发现了写的blog&＃xff0c;二分查找(Binary Search)需要注意的问题&＃xff0c;以及在数据库内核中的实现。
随想总结下二分查找的常见问题。
问题背景
今年的实习生招聘考试&＃xff0c;我出了一道二分查找(Binary Search)的题目。题目大意如下&＃xff1a;
给定一个升序排列的自然数数组&＃xff0c;数组中包含重复数字&＃xff0c;例如&＃xff1a;[1,2,2,3,4,4,4,5,6,7,7]。
问题&＃xff1a;给定任意自然数&＃xff0c;对数组进行二分查找&＃xff0c;返回数组正确的位置&＃xff0c;给出函数实现。
注&＃xff1a;连续相同的数字&＃xff0c;返回第一个匹配位置还是最后一个匹配位置&＃xff0c;由函数传入参数决定。
在这片博客中作者也详细说明了&＃xff0c;二分查找的重要性&＃xff0c;比如在数据库的内核实现中&＃xff0c;二分查找是一个非常重要的逻辑&＃xff0c;几乎99%以上的
SQL语句(所有索引上的范围扫描/等值查询/Unique查询等)&＃xff0c;都会使用到二分查找进行数据的定位。 可以看到二分查找在现实的重要性。
二分查找算法的思想
二分查找法主要是解决在“一堆数中找出指定的数”这类问题。
而想要应用二分查找法&＃xff0c;这“一堆数”必须有一下特征&＃xff1a;
所以如果是用链表
存储的&＃xff0c;就无法在其上应用二分查找法
了。 其实二分查找算法的思想很简单&＃xff0c;在《编程珠玑》一书中的描述&＃xff1a;
在一个包含x的数组内&＃xff0c;二分查找通过对范围的跟综来解决问题。开始时&＃xff0c;范围就是整个数组。通过将范围中间的元素
与x比较并丢弃一半范围&＃xff0c;范围就被缩小。这个过程一直持续&＃xff0c;直到在x被发现&＃xff0c;或者那个能够包含t的范围已成为空。
Donald Knuth在他的《Sorting and Searching》一书中指出&＃xff0c;尽管第一个二分查找算法早在1946年就被发表&＃xff0c;但第一个
没有bug的二分查找算法却是在12年后才被发表出来。
注意中间值下标的计算&＃xff0c;如果写成(low&＃43;high)/2&＃xff0c;low&＃43;high可能会溢出&＃xff0c;从而导致数组访问出错。改进的方法是将计算方式
写成如下形式&＃xff1a;low&＃43; ( (high-low) >>1)。
常见问题解决
在何登成的技术博客中的问题四 “如何查找第一个/最后一个等值”&＃xff0c;这个大牛只是简单的说明了下&＃xff0c;并没有详细说明怎么解决
这个问题&＃xff0c;下面来探讨 怎么解决 当所给有序重复数组 中查找 某个值出现的 第一个 和最后一个位置。
主要是下面三个问题&＃xff1a;
1&＃xff09;二分查找元素x的下标&＃xff0c;如无 return -1
2&＃xff09;二分查找返回x(可能有重复)第一次出现的下标&＃xff0c;如无return -1
3&＃xff09;二分查找返回x(可能有重复)最后一次出现的下标&＃xff0c;如无return -1
对于问题1 我们只需要 利用最原始的的二分查找即可。
代码如下&＃xff1a;
-
-
-
-
-
-
- int bin_search(int *a, int low, int high, int x)
- {
- if(NULL &＃61;&＃61; a || low > high)
- return -1;
-
- int mid;
- while(low<&＃61;high)
- {
- mid &＃61; low &＃43; ((high-low)>>1);
- if(x
- high &＃61; mid-1;
- else if(x>a[mid])
- low &＃61; mid &＃43;1;
- else
- return mid;
- }
- return -1;
- }
对于问题2&＃xff0c;二分查找返回x(可能有重复)第一次出现的下标&＃xff0c;如无return -1。
我们只需找到x重复出现情况下的第一次出现的下标。则我们只需用a[mid]和元素x进行比较&＃xff0c;当a[mid]
此时待查元素肯定在待查区间的右半部分 显然此时 不包括 mid 所以有 low &＃61; mid&＃43;1, 若a[mid]>&＃61;x时, 因为我
们查找的是x第一次出现的位置,我们不关心x最后出现的位置,所以此时high下标为mid,直到 low &＃61;&＃61; high 终止
循环&＃xff0c;并且比较a[low]是否为x,若是则 找到。
总的思路是&＃xff1a;
把有序序列分成2个序列:[first,mid][mid&＃43;1,last) 当 a[mid]
当 a[mid]>&＃61;x 时 使用序列[first,mid]。
还是看代码吧。
-
-
-
-
-
- int binS_first(int *a, int low, int high, int x)
- {
- if(NULL &＃61;&＃61; a || low > high)return -1;
- int mid;
- while(low
- {
- mid&＃61;low&＃43;((high-low)>>1);
- if(a[mid]
- low&＃61;mid&＃43;1;
- else
- high&＃61;mid;
- }
- if(a[low] &＃61;&＃61; x)
- return low;
- return -1;
- }
对于问题3&＃xff0c;二分查找返回x(可能有重复)最后一次出现的下标&＃xff0c;如无return -1
其实和问题2的思路差不多。
只是在 while中我们假定 low&＃43;1
接下来的while 情况和问题2等价。我们现在关心的是 x(可能有重复)最后一次出现的下标&＃xff0c;所以现在我们不关心他
第一次出现下标的位置, 当 a[mid]<&＃61;x 时 low &＃61; mid, 否则 a[mid] >x 此时 high &＃61; mid -1. 代码如下&＃xff1a;
-
-
-
-
-
-
- int binS_last(int *a, int low, int high, int x)
- {
- if(NULL &＃61;&＃61; a || low > high)
- return -1;
- int mid;
- while(low&＃43;1
- {
- mid&＃61;low&＃43;((high-low)>>1);
- if(a[mid]<&＃61;x)
- low &＃61; mid;
- else
- high&＃61;mid-1;
- }
- if(a[high] &＃61;&＃61; x)
- return high;
- else if(a[low] &＃61;&＃61; x)
- return low;
- return -1;
- }
查找重复元素出现的第一次 最后一次位置总结如下&＃xff1a;
二分查找返回x(可能有重复)第一次(最后一次)出现的下标找最小的等号放>&＃61;x位置(high),找最大的等号放<&＃61;x的位置(low)。
其中a[mid]在和待查找元素x比较中带 &＃61; 的&＃xff0c;在对low 或者high赋值时一定为 mid&＃xff0c;其它情况(<或>)则为mid&＃43;(-)1.
总的测试程序。
- #include
-
-
-
-
-
-
- int bin_search(int *a, int low, int high, int x)
- {
- if(NULL &＃61;&＃61; a || low > high)
- return -1;
-
- int mid;
- while(low<&＃61;high)
- {
- mid &＃61; low &＃43; ((high-low)>>1);
- if(x
- high &＃61; mid-1;
- else if(x>a[mid])
- low &＃61; mid &＃43;1;
- else
- return mid;
- }
- return -1;
- }
-
-
-
-
-
-
- int binS_first(int *a, int low, int high, int x)
- {
- if(NULL &＃61;&＃61; a || low > high)return -1;
- int mid;
- while(low
- {
- mid&＃61;low&＃43;((high-low)>>1);
- if(a[mid]
- low&＃61;mid&＃43;1;
- else
- high&＃61;mid;
- }
- if(a[low] &＃61;&＃61; x)
- return low;
- return -1;
- }
-
-
-
-
-
- int binS_last(int *a, int low, int high, int x)
- {
- if(NULL &＃61;&＃61; a || low > high)
- return -1;
- int mid;
- while(low&＃43;1
- {
- mid&＃61;low&＃43;((high-low)>>1);
- if(a[mid]<&＃61;x)
- low &＃61; mid;
- else
- high&＃61;mid-1;
- }
- if(a[high] &＃61;&＃61; x)
- return high;
- else if(a[low] &＃61;&＃61;x)return low;
- return -1;
- }
- int main()
- {
- int a[]&＃61; {-1,1,2,2,2,4,4,4,4,4,4,4};
- printf("-1: %d\n", bin_search(a, 0, 11, -1));
- printf(" 4 fisrt: %d\n", binS_first(a, 0, 11, 4));
- printf(" 4 last: %d\n", binS_last(a, 0, 11, 4));
- printf("\n");
- int b[]&＃61; {-2,-2,0,5,5,7,7};
- printf("-2 fisrt: %d\n", binS_first(b, 0, 6, -2));
- printf("-2 last: %d\n", binS_last(b, 0, 6, -2));
- printf(" 5 fisrt: %d\n", binS_first(b, 0, 6, 5));
- printf(" 5 last: %d\n", binS_last(b, 0, 6, 5));
- return 0;
- }
运行结果截图&＃xff1a;
此外对于像&＃xff0c;二分查找返回刚好小于x的元素下标&＃xff0c;二分查找返回刚好大于x的元素下标&＃xff0c; 返回有序数列某一个元素重复出现的次数等问题&＃xff0c;可以根据上面
的寻找重复元素出现第一次 最后一次位置的方法 进行 问题求解。对于这类问题也可以参考 STL 中关于 lower_bound与upper_bound的实现。STL算法库
中已经有相关实现。
参考&＃xff1a;
http://hedengcheng.com/?p&＃61;595
编程珠玑
http://blog.csdn.net/daniel_ustc/article/details/17307937
京公网安备 11010802041100号