二分查找BinarySearch

在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找是基于有序数据集合的查找算法，且数据结构必须为数组形式（能通过连续下标访问），比较适合处理中等批量的静态数据（无频繁更新、删除操作，且过大过小的数据量都不好）。

算法实现

普通版

def BinarySearch(arr, value):
	low = 0
	high = len(arr) - 1
	
	while low <= high: # 循环退出条件：`low <= high`，不是low < high
		# mid = int((low + high) / 2)
		# mid = left + int(right - left) // 2 
		mid = left + ((right-left)>>1) # 更高效的做法

		# 不推荐的判断方法
		'''
		if arr[mid] == value:
			return mid
		elif arr[mid] > value:
			high = mid - 1
		else:
			low = mid + 1
		'''

		# 因为 数组中不相等的情况更多，所以优先判断等于情况会更耗费资源，所以弃上取下
		# 推荐的判断方法
		if arr[mid] > value:
			high = mid -1 # 在左半区查找
		elseif arr[mid] < value:
			low = mid - 1 # 在右半区查找
		else:
			return mid

	return -1 # or None

递归版

def main(arr,value):
	rs = BinarySearch(arr, low=0, high=len(arr)-1, value=value)
	print(rs)

def BinarySearch(arr, low, high, value):
	if low > high: # 注意判断条件
		return -1

	mid = int((low + high) / 2)
	if arr[mid] == value:
		return mid
	elif arr[mid] > value:
		return BinarySearch(arr, low, mid - 1, value) # 一定要return，否则最终结果会是None
	else:
		return BinarySearch(arr, mid + 1, high, value) # 一定要return，否则最终结果会是None

算法趣事

虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。 ——乔恩·本特利，《编程珠玑（第1版）》