Python ❀ 二分查找

二分查找是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。

def binarySearch(arr,l,r,x):

#基础判断
if r >= l:
mid = int(l + (r -1) / 2)

#元素在中间位置
if arr[mid] == x:
return mid

#元素小于中间位置，左边查询
elif arr[mid] > x:
return binarySearch(arr,l,mid - 1,x)

#元素大于中间位置，右边查询
else:
return binarySearch(arr,mid + 1,r,x)

#元素不存在返回-1
else:
return -1

#输入数组和对应查询的值
arr = [2,1,3,4,5,6,73,3,23,5,6,7,3,2,6,6,7,2,33,1]
x = int(input("输入一个数字:"))

#函数调用
result = binarySearch(arr,0,len(arr)-1,x)

#输出索引值
if result != -1:
print("元素在数组中的索引为%s"%result)
else:
print("元素不在数组中")