Python 二分查找

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

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

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

Python 二分查找

# 返回 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 二分查找

上一篇:微信朋友圈如何同时分享(图片+文字) Android版


下一篇:[Android] 通过GridView仿微信动态添加本地图片