title: 二分搜索
tags: python,algorithm
二分搜索是程序员必备的小算法，无论什么场合，都要非常熟练地写出来。
小例子描述： 在有序数组arr中，指定区间[left,right]范围内，查找元素x 如果不存在，返回-1
二分搜索binarySearch实现的主逻辑
def binarySearch(arr, left, right, x):
while left <= right:
mid = int(left + (right - left) / 2); # 找到中间位置。求中点写成(left+right)/2更容易溢出，所以不建议这样写
# 检查x是否出现在位置mid
if arr[mid] == x:
print('found %d 在索引位置%d 处' %(x,mid))
return mid
# 假如x更大，则不可能出现在左半部分
elif arr[mid] < x:
left = mid + 1 #搜索区间变为[mid+1,right]
print('区间缩小为[%d,%d]' %(mid+1,right))
# 同理，假如x更小，则不可能出现在右半部分
elif x
right = mid - 1 #搜索区间变为[left,mid-1]
print('区间缩小为[%d,%d]' %(left,mid-1))
# 假如搜索到这里，表明x未出现在[left,right]中
return -1
在Ipython交互界面中，调用binarySearch的小Demo:
In [8]: binarySearch([4,5,6,7,10,20,100],0,6,5)
区间缩小为[0,2]
found 5 at 1
Out[8]: 1
In [9]: binarySearch([4,5,6,7,10,20,100],0,6,4)
区间缩小为[0,2]
区间缩小为[0,0]
found 4 at 0
Out[9]: 0
In [10]: binarySearch([4,5,6,7,10,20,100],0,6,20)
区间缩小为[4,6]
found 20 at 5
Out[10]: 5
In [11]: binarySearch([4,5,6,7,10,20,100],0,6,100)
区间缩小为[4,6]
区间缩小为[6,6]
found 100 at 6
Out[11]: 6
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/3711/viewspace-3159721/ ，如需转载，请注明出处，否则将追究法律责任。
