二分搜索算法及应用
什么是二分搜索算法
二分搜索（binary search）也称折半搜索（half-interval search）、对数搜索（logarithmic search），是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
==学习算法的三个步骤==
- 问题的形式化描述（问题是什么？输入输出是什么？）
- 算法设计
- 算法分析（正确性及复杂度分析）
二分搜索算法的各种情况
我们接下来讲的是==广义二分搜索算法==，我们讲这个的目的是想要尽可能用一种写法来基本普适各种情况，以便我们以后能够正确地记住并根据具体情况修改及使用该算法。
- 求下界，即找满足
x >= value或x > value条件的**最小x**的位置 - 求上界，即找满足
x <= value或x < value条件的**最大x**的位置
如果继续细分，还可以分为对非降序和非升序的数组进行求解。
十六种？
以寻找非降序数组内第一个不小于value值的最小x位置为例来说明算法：
二分搜索算法的实现思想
伪代码：
//返回[first，last)内第一个不小于value值的位置
//array是非降序数组
BINARYSEARCH(array，first，last，value){
while （first < last）: //搜索区间[first, last)不为空
mid = first + (last - first) /2 //防滥出
if (array[mid] < value)
first = mid + 1
else //array[mid] >= value
last = mid
return first //last也行，因为[first， last)为空的时候它们重合
}二分搜索算法相关分析
正确性证明
1、为什么使用左闭右开的参数
一切始于图灵奖得主==Dijkstra==（据说他不用纸笔只花了二十分钟就发明了著名的==迪杰斯特拉算法==），其大致思路如下：
假设有一个长度为4的数组,用整数边界的区间表示它的下标0,1,2,3,有四种写法:
a) 0≤i<4
b) -1<i≤3
c) 0≤i≤3
d) -1<i<4显然左边不闭的话-1 太丑了，所以只考虑a)和c)，然后怎么取舍呢?
现在假设该数组长度慢慢减小到0，右边界减小，此时它的index范围是空集$\emptyset$,整数边界的区
间的四种写法变成了:
a) 0≤i<0
b) -1<i≤-1
c) 0≤i≤-1
d) -1<i<0现在只有a)不会出现负数了。看来左闭右开的a)是唯一种不反人类的写法!它还有一些个
好处:
1.区间两端值的差，如[0, 4) 中的4-0=4,正好是区间或数组的长度
2.刚好相邻的区间，如[0, 2)和[2, 4)，中间值(即2)相同,一眼就可以看出来
2、如何取中点
如果用mid = (first + last)/2计算中点，在C++、JAVA等语言里可能会出现溢出现象。
解决方案就是将其改写成mid = first + (last - first)/2的写法，其中lenth = last - first为区间长度。
此外，中点的选择并不唯一，
1、上位中位数：upperMid = first + length/2
2、下位中位数：lowerMid = first + (length - 1)/2
由于下位中位数还需要减一，用起来怪麻烦，所以我们选择使用上位中位数。
3、while里的循环不变量 - loop invariants
代码进入while循环里面时一定成立的条件：
- 搜索范围
[first, last)不为空，即first < last； - 搜索范围左侧所有元素都小于value（若存在），搜索范围右侧所有元素都大于等于value（若存在）。
4、 本算法中，当[first,last)为空的时候first与last重合
综合1、2、3，当[first,last)为空的时候first与last重合且该值即为第一个不小于value值的位置
为什么：因为算法的最终一定会收敛到区间first=last的结束，在该最终步的上一步的while循环里，根据循环不变量，我们再分析该区间长度为1的区间缩小策略，就可以得出结论。
最好，我们需要说明，该算法其实没必要必须是非降序，只需要value值两侧的部分是数组的一个划分就可以满足循环不变量，说人话就是我们要找的元素的左侧的元素都小于value值，右侧元素都大于等于value值即可。
5、举例
6、 其他情况算法变化
==这个广义的二分算法，只要value是这个数组的一个划分就可以了。==
==对于非降序数组==
- 找满足
x > value条件的**最小x**的位置
根据以上分析，将if条件改为小于等于即可
- 找满足
x <= value条件的**最大x**的位置
情况1得到的位置再减一即可
- 找满足
x < value条件的**最大x**的位置
我们讨论的寻找非降序数组内第一个不小于value值的位置的情况得到的位置再减一即可。
……
==对于非增序数组==
- 通过对while循环最后一步的分析修改红框里箭头处的三个条件
- 将数组反序后求非降序数组的镜像位置之后再求出原问题的位置
分析一个例子：
求非增序数组x >= value的x的最大位置（给定value为3）
分析while循环的最后一步，考虑如何设置if条件和返回值：
由分析可得相应算法：
//返回[first，last)内第一个不小于value值的位置
//array是非降序数组
BINARYSEARCH(array，first，last，value){
while （first < last）: //搜索区间[first, last)不为空
mid = first + (last - first) /2 //防滥出
if (array[mid] >= value)
first = mid + 1
else //array[mid] < value
last = mid
return first-1 //last-1也行，因为[first， last)为空的时候它们重合
}……
时间复杂度分析
O(logn)
