vlambda博客
学习文章列表

因此，从最基本的方面对二分查找做个总结，本篇是二分查找的第一篇，后续还会有比较深入的讨论，计划一共写三篇。

第一部分，二分查找的约束条件

def binary_search(list, item): left = 0 right = len(list) - 1 while left <= right: mid = int(((right-left) >> 1) + left) guess = list[mid] if guess == item: return mid if guess > item: right = mid - 1 else: left = mid + 1 return None

1.  二分查找的循环条件是 left<=right
1. 这里是以升序列表为例，left是小，right是大，当left=right的时候，二分查找还没有完成最后一个元素的比较，因此还需要循环最后一次；
2. 找中间位置的方法不同于常规的做法
1. （低位+高位）/ 2 取整
2. （高位-低位）/2 + 低位 取整
3. 而是用了二进制移位符 >> 来直接进行二进制的移位完成了除以2的操作，比用除法，性能要好一些。二进制数移动一位相当于十进制数除以2，这里要注意下>>的优先级，如果写成left+(right-left) >> 1的话，二分查找就会变成死循环了，大家可以自己亲自动手试试，找到其中的原因。
   
3. 当二分位置上元素的数值和要查找的元素的数值不一致的时候，低位和高位的处理方法要根据是升序列表还是将序列表来决定。

1. 如果目标值item>List[mid]，则Left += 1，此时目标值应该插入到Left的位置，如insert(left, item);

2. 如果目标值item<List[mid]，则Right -= 1，此时目标值小于例表中Left位置的元素，目标职业需要插入到Left的位置，如insert(left, item)

所以，可以看出，如果查询不到目标值，则应该返回Left的位置。代码如下：

def binary_search(list, item): left = 0 right = len(list) - 1 while left <= right: mid = int(((right - left)>>1) +left) guess = list[mid] if guess < item: left = mid + 1 elif guess >= item: right = mid - 1    return left