#二分查找法：
二分搜索是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。
方法一：（while循环法）
def binarySearch(arr,x): #自定义函数：arr:有序数组；x:待查找值
low,high=0,len(arr)-1 #初始查询下标索引
while low<=high: #循环判断
mid=int((low+high)/2) #获取有序数组中间值下标索引
if x==arr[mid]: #判断待查找值与中间索引值相同
return mid #返回索引下标
elif x>arr[mid]: #判断待查值大于中间索引值时
low=mid+1 #开始索引下标赋新值
else: #判断待查值小于中间索引值时
high=mid-1 #结束索引下标赋新值
return -1 #while循环判断不成立时
#测试
arr=[2,3,4,10,40]
x=10
result=binarySearch2(arr,x)
print(result)
方法二：（递归法）
def binarySearch(arr,s,e,x): #自定义递归函数 arr:有序数组，s：开始索引下标，e:结束索引下标，x：待查值
if s<=e: #循环判断
mid=int((e+s)/2) #获取有序数组中间值下标索引
if arr[mid]==x: #判断待查找值与中间索引值相同
return mid #返回索引下标
elif arr[mid] < x: #判断待查值大于中间索引值时
return binarySearch(arr,mid+1,e,x) #递归：开始索引下标赋新值
else: #判断待查值小于中间索引值时
return binarySearch(arr,s,mid-1,x) #递归：结束索引下标赋新值
else: #外层 if 循环判断不成立时
return -1
#测试数组
arr=[2,3,4,10,40]
x=10
#函数调用
result=binarySearch(arr,0,len(arr)-1,x)
print(result)