二分搜索是一种在有序数组中查找特定元素的搜索算法。

搜索过程中从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，并且跟开始一样，从中间元素开始比较。

当数组为空时，表示找不到。这种搜索算法每次比较都使范围缩小一半。

# 返回 x 在 arr 中的索引，如果不存在返回 -1
def binarySearch(arr, s, e, x):
	if e >= s:
		mid = int(s + (e-s)/2)
		if arr[mid] == x:			# 元素是中间位置
			return mid
		elif arr[mid] > x:
			return binarySearch(arr, s, mid-1, x)	# 元素小于中间位置
		else:
			return binarySearch(arr, mid+1, e, x)	# 元素大于中间位置

	else:	# 不在数组中
		return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binarySearch(arr, 0, len(arr)-1, x)
print(result)

输出结果：

3

Python 二分查找