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