首先我们来回忆一下基本的二分查找，二分查找是什么呢，主要用在从一个已经排序的序列中找到给定的数字的索引。

假设数组内的元素都是不严格的升序排列，
首先写一个基本的递归法二分查找。

如果能找到就返回相应的索引，否则就返回-1。这里left和right都是包含在搜索范围内的。

def binary_search(x,arr,left,right):
    if right<left: 
	    return -1
    mid=(left+right)/2
	if arr[mid]==x:
	    return mid
	if x<arr[mid]:
	    return binary_search(x,arr,left,mid-1)
	return binary_search(x,arr,mid+1,right)

对应的二叉搜索树👆

如果找到就会直接返回索引，找不到就会进入下面的粉(?)色方框中,返回-1。

代码也可以写成非递归的形式：

def binary_search(x,arr,left,right):
    while right>=left: 
        mid=(left+right)/2
	    if arr[mid]==x:
	        return mid
	    if x<arr[mid]:
	        right=mid-1
		else:
	        left=mid+1
	return -1

我们来分析一下这棵二叉搜索树的索引们，特别是未找到的索引。

如果搜索时没有找到，进入了方框中。要进入方框，那么一定是和某个与方框节点相连的圆形节点进行了比较。此时这个圆形节点就是arr[mid]。

如果是向左走，那么其left是没有变化的，也就是mid，right变为了mid-1。arr[mid]是一个比x大的数，而且是第一个比x大的数。right即mid-1是最后一个比x小的数。

同理，如果是向右走，right不变，仍然是mid，left变为了mid+1。arr[mid]是一个比x小的数，而且是最后一个比x小的数。而left代表的arr[mid+1]也就是第一个大于x的数。

那么，如果我们想求不大于x的最后一个数，也就是小于等于x的最后一个数的索引，应该怎么求呢？

def binary_search(x,arr,left,right):
    if right==left: 
	    if arr[left]<=x:
		    return left
		return left-1
    mid=(left+right)/2
	if arr[mid]==x:
	    return mid
	if x<arr[mid]:
	    return binary_search(x,arr,left,mid-1)
	return binary_search(x,arr,mid+1,right)

但是这么写就不是非常有水平，毕竟循环条件不是在right==left时终止的嘛！

所以再回去看看原来的分析：
当我们要求小于等于x的最后一个数时，如果是走了左边的分支，说明arr[mid]>x，而我们应该返回的小于等于x的最后一个数应该不是mid，而是mid-1，left=原mid，right=原mid-1，我们应该返回的数就是mid，所以返回right。
如果走了右边的分支，小于等于x的最后一个数应该就是arr[mid]，那么right=原mid，left=原mid+1，返回right。

def binary_search(x,arr,left,right):
    if right<left: 
	    return right
    mid=(left+right)/2
	if arr[mid]==x:
	    return mid
	if x<arr[mid]:
	    return binary_search(x,arr,left,mid-1)
	return binary_search(x,arr,mid+1,right)

迭代形式如下:

def binary_search(x,arr,left,right):
	while right>=left:
        mid=(left+right)/2
	    if arr[mid]==x:
	        return mid
	    if x<arr[mid]:
	        right=mid-1
	    else:
		    left=mid+1
	return right

同理我们也可以写出求不小于x的第一个数，返回left即可~

def binary_search(x,arr,left,right):
	while right>=left:
        mid=(left+right)/2
	    if arr[mid]==x:
	        return mid
	    if x<arr[mid]:
	        right=mid-1
	    else:
		    left=mid+1
	return left

也有人会更喜欢前闭后开的表示方式，但个人觉得那样会比较容易混淆，所以喜欢前闭后闭这样写一些。

前闭后开普通：

def binary_search(x,arr,left,right):
    while right>left: 
        mid=(left+right)/2
	    if arr[mid]==x:
	        return mid
	    if x<arr[mid]:
	        right=mid
		else:
	        left=mid+1
	return -1

前闭后开查询大于等于x的第一个数。查询到最后一个方块时，如果是左方块，left=前mid，right也等于前mid，要返回的数也是前mid。如果是右方块，left=right=前mid+1，要返回的也是前mid+1。

def binary_search(x,arr,left,right):
	while right>left:
        mid=(left+right)/2
	    if arr[mid]==x:
	        return mid
	    if x<arr[mid]:
	        right=mid
	    else:
		    left=mid+1
	return left

前开后闭查询小于等于x的最后一个数。查询到最后一个方块时，如果是左方块，left=right=前mid-1，要返回的数也是前mid-1。右方块，left=right=前mid，要返回的也是前mid。

def binary_search(x,arr,left,right):
	while right>left:
        mid=(left+right+1)/2
	    if arr[mid]==x:
	        return mid
	    if x<arr[mid]:
	        right=mid-1
	    else:
		    left=mid
	return left

为了不溢出，我们最好用

mid=left+(right-left)/2