二分查找

查找题目的套路：

• 根据辅助变量found来判断是否已经找到target。
• 每次查找到item都会有三种情况：item等于target，item小于target，item大于target。然后就是每种情况下，如何改变查找条件。

一、二分搜索

二分搜索的是有序表，时间复杂度是O(log(n))。需要一个辅助变量found来表示是否已经找到target。
思路：
1、左指针为left，右指针为right，中间指针为len(list)//2。

2、有序，选择中间元素item，与target进行比较，相应的有三种情况

• target等于item，结束搜索，返回True
• target小于中间的数item，说明target在左半部分，下一步应该在左半部分索引，即在[left : mid-1]部分索引，于是将right赋值为mid-1，继续下一步的循环。
• target大于中间的数item，说明target在右半部分，下一步应该在右半部分索引，即在[mid+1 : right]部分索引，于是将left赋值为mid+1，继续下一步的循环。
• 4、循环，直到找到。

代码：

循环条件：左指针小于等于右指针，且没有发现target

1   def binarySearch(alist, target):
        #定义左指针跟右指针的索引
2       first = 0
3       last = len(alist)-1
        #把found设置为Flase
4       found = False
5   
6       while first<=last and not found:
7           midpoint = (first + last)//2
8           if alist[midpoint] == target:
9               found = True
10          else:
11              if target < alist[midpoint]:
12                  last = midpoint-1#target在左半部分
13              else:
14                  first = midpoint+1
16      return found

递归版本：用列表切片来限制搜索范围

1   def binarySearch(alist, target):
2       if len(alist) == 0:
3           return False
4       else:
5           midpoint = len(alist)//2
6           if alist[midpoint]==target:
7             return True
8           else:
9             if target<alist[midpoint]:
10              return binarySearch(alist[:midpoint],target)
11            else:
12              return binarySearch(alist[midpoint+1:],target)
13  
14  testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
15  print(binarySearch(testlist, 3))
16  print(binarySearch(testlist, 13))