输入：一个已经排好序的待搜索数组array_to_search，需要查找的数number，查找边界left、right。
输出：number在array_to_search中的位置，若未找到，输出-1。
实现思路
- 将数组的中间元素array_to_search[middle]与待查找数number进行比较，如果相等，则成功找到，结束；
- 若array_to_search[middle] > number，则number只可能出现在array_to_search的前半段，放弃对后半段的查找，查找规模减半，回到步骤1；
- 若array_to_search[middle] < number，则number只可能出现在array_to_search的后半段，放弃对前半段的查找，查找规模减半，回到步骤1；
- 若查找规模 = 1时仍然没有查找到number，则待查找数组中没有number，结束。
两个例子
查找成功
输入：array_to_search = [1, 7, 12, 16, 24, 28, 34, 39]，number = 34， left = 0， right = 7
-
middle = (0 + 7) // 2 = 3，array_to_search[middle ] = 16， 小于number，array_to_search变成如下状态：
[1, 7, 12, 16, 24, 28, 34, 39] -
middle = (4 + 7) // 2 = 5，array_to_search[middle ] = 28，小于number，array_to_search变成如下状态：
[1, 7, 12, 16, 24, 28, 34, 39] -
middle = (6 + 7) // 2 = 6， array_to_search[middle ] = 34，等于number，算法结束
查找失败
输入：array_to_search = [1, 7, 12, 16, 24, 28, 34, 39]，number = 3， left = 0， right = 7
-
middle = (0 + 7) // 2 = 3，array_to_search[middle ] = 16， 大于number，array_to_search变成如下状态：
[1, 7, 12, 16, 24, 28, 34, 39] -
middle = (0 + 2) // 2 = 1，array_to_search[middle ] = 7，大于number，array_to_search变成如下状态：
[1, 7, 12, 16, 24, 28, 34, 39] -
middle = (0 + 0) // 2 = 0，array_to_search[middle ] = 1，小于number，由于问题规模已经为1，算法结束，查找失败。
流程图
二分查找完整算法（Python实现）
from random import uniform
def binary_search(array_to_search, number, left, right):
index = -1
while(left <= right):
middle = (left + right) // 2
if array_to_search[middle] == number:
index = middle
break
elif array_to_search[middle] > number:
right = middle - 1
else:
left = middle + 1
return index
if __name__ == '__main__':
array_size = int(input("Please input the length of array:"))
array_to_search = [int(uniform(0, 5)) + 5 * i for i in range (0, array_size)]
print("Init array:", array_to_search)
number = int(input("Please input the number you want to search:"))
# start search
print("
")
print("######################")
print("## Start searching! ##")
print("######################")
print("")
print("Binary Search:", binary_search(array_to_search, number, 0, len(array_to_search)))
时间复杂度
对于一个长度为n的数组，每次与中间元素进行比较后规模都将缩小为原来的(frac{1}{2})，因此经过(log_2n)次比较后，规模将会缩小为1，因此二分查找的时间复杂度为(O(log_2n))。
OJ(LeetCode 852.山脉数组的峰值索引)
我们把符合下列属性的数组A称作山脉：
- A.length >=3
- 存在0 < i < A.length - 1使得A[0] < A[1] < ... < A[i - 1] < A[i] > A[i + 1] > ... > A[A.length - 1]
给定一个确定为山脉的数组，返回任何满足任何满足A[0] < A[1] < ... < A[i - 1] < A[i] > A[i + 1] > ... > A[A.length - 1]的i的值。
按照算法的标准可以描述成如下形式：
输入：一个符合A[0] < A[1] < ... < A[i - 1] < A[i] > A[i + 1] > ... > A[A.length - 1]的数组A。
输出：i。
一种朴素的想法是遍历数组，当某一个i使得A[i - 1] < A[i]并且A[i] > A[i + 1]，则i即为所求。显然这种方法的时间复杂度为(O(n))。
我们可以采用二分查找的思想，每次取查找范围最中间的数A[mid]，观察A[mid - 1]、A[mid]、A[mid + 1]三者的关系，如果A[mid - 1] < A[mid] && A[mid] > A[mid + 1]，则mid为山峰的索引；若A[mid - 1] < A[mid] && A[mid] < A[mid + 1]，证明还在上坡过程，mid在山峰的左边，查找范围缩小到[mid + 1, right]；否则则为下坡过程，mid在山峰的右边，查找范围缩小到[left, mid - 1]。这种方法的时间复杂度为(O(log_2n))。
山脉数组的峰值索引完整算法(C++实现)
class Solution {
public:
int peakIndexInMountainArray(vector<int>& A) {
int length = A.size();
int left = 0, rigth = length - 1;
int mid = 0, current = 0;
while(left <= rigth)
{
mid = (left + rigth) / 2;
if(A[mid - 1] < A[mid] && A[mid] > A[mid + 1])
{
break;
}
else if(A[mid - 1] < A[mid] && A[mid] < A[mid + 1])
{
left = mid + 1;
}
else
{
rigth = mid - 1;
}
}
return mid;
}
};