二分查找

算法思想：

假设表中元素是按升序排列，

将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；

否则利用中间位置记录将表分成前、后两个子表，

如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，

否则进一步查找后一子表。

重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

举例：

序列：1 2 3 5 7 9 10 储存在a数组中

要查找关键字为 2

1. a数组*7个元素，low=0，high=6，mid=(low+high)/2=3  则将 2 与 a[mid] 进行比较，有a[mid]>2，所以在0 ~ mid-1的序列中查找

2.low=0，high=mid-1, mid=(low+high)/2 =1 a[mid]=2，所以查找成功。

算法分析：

共n个元素，每一次查找即可以排除当前序列一半的元素（宛如灭霸打了个响指）。随着查找次数的增加，查找范围缩小为n/2，n/4，n/8，n/16 ......

最坏情况需要 2^t=n ,即需以2为底logn次，所以时间复杂度是 logn

代码：

def binarySearch(lista, item):
   low = 0
   high=len(lista)-1
   while(low<=high):
       mid = int( (high+low)/2)
       if item > lista[mid]:
           low = mid + 1
       elif item < lista[mid]:
           high = mid-1
       else:
           return mid
   return  -1