博主地址：
二分查找，最基本的算法之一，也是面试中常被考察的重点，因为基本的算法最能反映出一个人的基础是否扎实。本文对二分查找相关题目做一个总结。
题目列表：
这个是最原始的二分查找题目，利用数组的有序特性，拆半查找，使得查找时间复杂度为O(logN)。请参考实现代码与注释。
此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找，如果不存在直接返回-1，如果存在，然后再顺序找到这个等于target值区间的最左位置，这样的话，最坏情况下的复杂度就是O（n）了，没有完全发挥出二分查找的优势。这里的解法具体过程请参考实现代码与注释。
此题也就是求target在数组中最后一次出现的位置。与上一题基本一样，但是有个地方要注意，具体请参考实现代码与注释。
也就是求小于target的最大元素的位置。请参考实现代码与注释。
也就是求大于target的最小元素的位置。请参考实现代码与注释。
求出第一次出现位置和最后一次出现位置。由于前面都已实现，这里不多解释。请参考实现代码与注释
此题描述或者改为求目标值在数组中的索引范围。
如 & &[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0
找第一个大于等于0的位置，然后和前一个元素的绝对值比较，返回绝对值较小的元素的位置。请参考实现代码与注释
这个题目出现了两个数组，有序的，不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找，时间复杂度最低为O(k)，就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。
1 2 4 5 6 7&可能变成&4
5 6 7 0 1 2
我们先比较中间元素是否是目标值，如果是返回位置。如果不是，我们就应该想办法将搜索区间减少一半。因为存在旋转变化，所以我们要多做一些判断。我们知道因为只有一次旋转变化，所以中间元素两边的子数组肯定有一个是有序的，那么我们可以判断target是不是在这个有序的子数组中，从而决定是搜索这个子数组还是搜索另一个子数组。具体请参考实现代码与注释。
如果这样的数组中存在重复元素，还能使用二分吗？答案是不能。请看几个例子
[1, 2, 2, 2, 2], [2, 1, 2, 2, 2], [2, 2, 1, 2, 2], [2, 2, 2, 1, 2], [2, 2, 2, 2, 1]这些都是有第一个数组旋转一次变化来的，我们不能通过二分确定是否存在元素1.
如果中间元素小于左端元素，则最小值在左半区间内（包含中间元素）；如果中间元素大于右端元素，则最小值在右半区间内（包含中间元素）。请参考实现代码与注释。
我们可以利用上一题的解答，求出最小值所在位置后，便可以求出第k小元素。请参考实现代码与注释
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：18140次
排名：千里之外
原创：51篇
(2)(7)(1)(1)(1)(1)(5)(10)(13)(1)(2)(8)(1)(2)(2)3680人阅读
c/c++/cpp11（12）
数据结构、算法（27）
今天浏览 & 无意中发现了写的blog，。
随想总结下二分查找的常见问题。
今年的实习生招聘考试，我出了一道二分查找(Binary Search)的题目。题目大意如下：
给定一个升序排列的自然数数组，数组中包含重复数字，例如：[1,2,2,3,4,4,4,5,6,7,7]。
问题：给定任意自然数，对数组进行二分查找，返回数组正确的位置，给出函数实现。
注：连续相同的数字，返回第一个匹配位置还是最后一个匹配位置，由函数传入参数决定。
&在这片博客中作者也详细说明了，二分查找的重要性，比如在数据库的内核实现中，二分查找是一个非常重要的逻辑，几乎99%以上的
SQL语句(所有索引上的范围扫描/等值查询/Unique查询等)，都会使用到二分查找进行数据的定位。 可以看到二分查找在现实的重要性。
二分查找算法的思想
主要是解决在“一堆数中找出指定的数”这类问题。
而想要应用二分查找法，这“一堆数”必须有一下特征：
存储在数组中有序排列
所以如果是用存储的，就无法在其上应用了。
其实二分查找算法的思想很简单，在《编程珠玑》一书中的描述：
&在一个包含x的数组内，二分查找通过对范围的跟综来解决问题。开始时，范围就是整个数组。通过将范围中间的元素
与x比较并丢弃一半范围，范围就被缩小。这个过程一直持续，直到在x被发现，或者那个能够包含t的范围已成为空。
&Donald Knuth在他的《Sorting and Searching》一书中指出，尽管第一个二分查找算法早在1946年就被发表，但第一个
没有bug的二分查找算法却是在12年后才被发表出来。
注意中间值下标的计算，如果写成(low+high)/2，low+high可能会溢出，从而导致数组访问出错。改进的方法是将计算方式
写成如下形式：low+ ( (high-low) &&1)。
常见问题解决
在中的问题四 “如何查找第一个/最后一个等值”，这个大牛只是简单的说明了下，并没有详细说明怎么解决
这个问题，下面来探讨 怎么解决 当所给有序重复数组 中查找 某个值出现的 第一个 和最后一个位置。
主要是下面三个问题：
1）二分查找元素x的下标，如无 return& -1
2）二分查找返回x(可能有重复)第一次出现的下标，如无return& -1
3）二分查找返回x(可能有重复)最后一次出现的下标，如无return& -1
对于问题1 我们只需要 利用最原始的的二分查找即可。
代码如下：
bin_search 二分查找元素x的下标，如无 return -1
low,high 分别为待查元素的区间的 上下界(包含边界).
x为待查元素.
注意 low &= high
int bin_search(int *a, int low, int high, int x)
if(NULL == a || low & high)
return -1;
while(low&=high)//注意是&=，若是&会找不到边界值情况
mid = low + ((high-low)&&1);
if(x&a[mid])
high = mid-1;
else if(x&a[mid])
low = mid +1;
return -1;
对于问题2，二分查找返回x(可能有重复)第一次出现的下标，如无return& -1。
我们只需找到x重复出现情况下的第一次出现的下标。则我们只需用a[mid]和元素x进行比较，当a[mid]&x时
此时待查元素肯定在待查区间的右半部分 显然此时 不包括 mid 所以有 low = mid+1, 若a[mid]&=x时, 因为我
们查找的是x第一次出现的位置,我们不关心x最后出现的位置,所以此时high下标为mid,直到 low == high 终止
循环，并且比较a[low]是否为x,若是则 找到。
总的思路是：
把有序序列分成2个序列:[first,mid][mid+1,last) 当 a[mid]&x 时 使用&使用序列[mid + 1,last)
当 a[mid]&=x 时 使用序列[first,mid]。
还是看代码吧。
binS_first二分查找返回x(可能有重复)第一次出现的下标，如无return -1
low,high 分别为待查元素的区间的 上下界(包含边界).
//分成2个序列:[first,mid][mid+1,last)
& x为待查元素.注意 循环结束条件，low == high */
int binS_first(int *a, int low, int high, int x)
if(NULL == a || low & high)return -1;
while(low&high)
mid=low+((high-low)&&1);//计算中点
if(a[mid]&x)// &x ,调整起点或者终点
low=mid+1;
else // &=x
if(a[low] == x)
return -1;
对于问题3，二分查找返回x(可能有重复)最后一次出现的下标，如无return& -1
其实和问题2的思路差不多。
只是在 while中我们假定 low+1 & high,否则在只有两个或者一个元素时 我们只需在while循环之外判断即可。
接下来的while 情况和问题2等价。我们现在关心的是 x(可能有重复)最后一次出现的下标，所以现在我们不关心他
第一次出现下标的位置, 当 a[mid]&=x 时 low = mid, 否则 a[mid] &x 此时 high = mid -1. 代码如下：
binS_last二分查找返回x(可能有重复)最后一次出现的下标,如无return -1
low,high 分别为待查元素的区间的 上下界(包含边界).
x为待查元素.
注意 循环结束条件，low+1 == high
int binS_last(int *a, int low, int high, int x)
if(NULL == a || low & high)
return -1;
while(low+1&high)//**
mid=low+((high-low)&&1);
if(a[mid]&=x)
high=mid-1;
if(a[high] == x)//先判断high
else if(a[low] == x)
return -1;
查找重复元素出现的第一次 最后一次位置总结如下：
二分查找返回x(可能有重复)第一次(最后一次)出现的下标找最小的等号放&=x位置(high),找最大的等号放&=x的位置(low)。
其中a[mid]在和待查找元素x比较中带 = 的，在对low 或者high赋值时一定为 mid，其它情况(&或&)则为mid+(-)1.
总的测试程序。
#include &stdio.h&
bin_search 二分查找元素x的下标，如无 return -1
low,high 分别为待查元素的区间的 上下界(包含边界).
x为待查元素.
注意 low &= high
int bin_search(int *a, int low, int high, int x)
if(NULL == a || low & high)
return -1;
while(low&=high)//注意是&=，若是&会找不到边界值情况
mid = low + ((high-low)&&1);
if(x&a[mid])
high = mid-1;
else if(x&a[mid])
low = mid +1;
return -1;
binS_first二分查找返回x(可能有重复)第一次出现的下标,如无return -1
low,high 分别为待查元素的区间的 上下界(包含边界).
//分成2个序列:[first,mid][mid+1,last)
x为待查元素.
注意 循环结束条件，low == high */
int binS_first(int *a, int low, int high, int x)
if(NULL == a || low & high)return -1;
while(low&high)//&
mid=low+((high-low)&&1);
if(a[mid]&x)// &x
low=mid+1;
else // &=x
if(a[low] == x)
return -1;
binS_last二分查找返回x(可能有重复)最后一次出现的下标,
如无return -1
low,high 分别为待查元素的区间的 上下界(包含边界).
x为待查元素.注意 循环结束条件，low+1 == high */
int binS_last(int *a, int low, int high, int x)
if(NULL == a || low & high)
return -1;
while(low+1&high)//**
mid=low+((high-low)&&1);
if(a[mid]&=x) // &=x
else // &x
high=mid-1;
if(a[high] == x)//先判断high
else if(a[low] ==x)
return -1;
int main()
int a[]= {-1,1,2,2,2,4,4,4,4,4,4,4}; //0-11
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[]= {-2,-2,0,5,5,7,7}; //0-6
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));
运行结果截图：
&&&&&&&&&&&&&&&&&&&&
此外对于像，二分查找返回刚好小于x的元素下标，二分查找返回刚好大于x的元素下标， 返回有序数列某一个元素重复出现的次数等问题，可以根据上面
的寻找重复元素出现第一次 最后一次位置的方法 进行 问题求解。对于这类问题也可以参考 STL 中关于 lower_bound与upper_bound的实现。STL算法库
中已经有相关实现。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：412627次
积分：5441
积分：5441
排名：第4554名
原创：105篇
转载：17篇
评论：96条
-------------------------------------------- --------------------------------------------
阅读：15654
(2)(4)(1)(3)(1)(3)(4)(8)(7)(9)(10)(3)(5)(6)(4)(1)(9)(4)(4)(8)(10)(4)(5)(5)(1)(1)数据结构（18）
说明及代码如下：
本例用来实现对分查找：
对分查找：给定一个整数X和一列已经排好序的整数，查找X是否在这列整数中，若在，则返回整数
在这列整数中的位置;若不在，则返回-1
#include &iostream&
int BinarySearch(int a[], int n, int X);
int main()
// 整数的个数
//存放我们输入的用来寻找的数字
cout && &Enter the number of integers: &;
//定义一个数组来存放这些整数
for(int i=0; i&N; i++)
cin && a[i];
//输入一列排好序的整数，这里假定我们输入的是从小到大的整数
cout && &Enter the integer you want to search: &;
int result = BinarySearch(a, N, num);
cout && &The return value is & && result&&
int BinarySearch(int a[], int n, int X)
//参数为一个有n个元素的数组，在其中查找是否含有X
int low = 0, middle, high = n - 1;
while(low &= high)
middle = (low + high) / 2;
if(X & a[middle])
low = middle + 1;
else if(X & a[middle])
high = middle - 1;
return middle + 1;
return -1;
运行结果：
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：47672次
积分：1204
积分：1204
排名：千里之外
原创：72篇
转载：13篇
(6)(7)(2)(6)(1)(15)(17)(31)匿名用户不能发表回复！|
每天回帖即可获得10分可用分！小技巧：
你还可以输入10000个字符
(Ctrl+Enter)
请遵守CSDN，不得违反国家法律法规。
转载文章请注明出自“CSDN（www.csdn.net）”。如是商业用途请联系原作者。&&&&二分查找又称折半查找，它是一种效率较高的查找方法。
&&&&二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。
2、基本思想
&&&&二分查找的基本思想是：
&&&&设R[low..high]是当前的查找区间
&（1）首先确定该区间的中点位置：
& & & & & & & & &&
&（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：
&&&&① &若R[mid].key&K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。
&&&&② &若R[mid].key&K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。
&&&&因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。
3、存储结构
&&&&二分查找只适用顺序存储结构。
4、二分查找算法
/*折半查找*/
int Binary_Search(int a*,int n,int key)
int low,high,
/*定义最底下标为记录首位*/
/*定义最高下标为记录末位*/
while(low&=high)
mid=(low+high)/2;
if(key&a[mid])
high=mid-1;
if(key&a[mid])
low=mid+1;
也可以如下构造参数：
int BinSearch(SeqList R，KeyType K)
//在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零
int low=1;
int high=n;
//置当前查找区间上、下界的初值
while(low&=high)
//当前查找区间R[low..high]非空
mid=(low+high)/2；
if(R[mid].key==K)
return mid；
//查找成功返回
if(R[mid].kdy&K)
high=mid-1;
//继续在R[low..mid-1]中查找
low=mid+1；
//继续在R[mid+1..high]中查找
//当low&high时表示查找区间为空，查找失败
5、算法分析
① &执行过程&
&&&&设算法的输入实例中有序的关键字序列为
(05，13，19，21，37，56，64，75，80，88，92)
二分查找判定树
&&&&二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。
&&&&注意：
&&&&判定树的形态只与表结点个数n相关，而与输入实例中R[1..n].keys的取值无关。
&&&&（1）二分查找判定树的组成
&&&&①圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。
&&&&②外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。
&&&&③树中某结点i与其左(右)孩子连接的左(右)分支上的标记"&"、"("、"&"、")"表示：当待查关键字K&R[i].key(K&R[i].key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。
&&&&（2）二分查找判定树的查找
&&&&二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等，成功。否则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。
&&&&【例】对于有11个结点的表，若查找的结点是表中第6个结点，则只需进行一次比较；若查找的结点是表中第3或第9个结点，则需进行二次比较；找第1，4，7，10个结点需要比较三次；找到第2，5，8，11个结点需要比较四次。
&&&&由此可见，成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径，经历比较的关键字次数恰为该结点在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。
&&&&【例】待查表的关键字序列为：(05，13，19，21，37，56，64，75，80，88，92)，若要查找K=85的记录，所经过的内部结点为6、9、10，最后到达方形结点"9-10"，其比较次数为3。
&&&&实际上方形结点中"i-i+1"的含意为被查找值K是介于R[i].key和R[i+1].key之间的，即R[i].key&K&R[i+1].key。
② &二分查找的平均查找长度
&&&&设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为：
& & & & & &ASLbn&lg(n+1)-1
&&&&二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为：
& & & & & &&
&&&&二分查找的最坏性能和平均性能相当接近。
③ &二分查找的优点
&&&&折半查找的时间复杂度为O(logn)，远远好于顺序查找的O(n)。
④ &二分查找的缺点
&&&&虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。
⑤ &适用情况
&&&&二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
&&&&对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。
阅读(...) 评论()