二分查找及其变体

　　二分查找算法是针对有序数据集合的查找算法，也叫折半查找算法：每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。二分查找的最好时间复杂度是O(1)，最坏时间复杂度是O(logn)，这种对数时间复杂度极其高效，有时甚至比O(1)的算法还要高效。

1.最简单的二分查找法(不含重复的元素)代码实现：

1.1.递归形式

 1 def binary_search(alist, item):
 2     """二分查找---递归版本"""
 3     n = len(alist)
 4     if n > 0:  # 递归终止条件，区间没有元素
 5         mid = n // 2  # 中间位置
 6         if alist[mid] == item:
 7             return True
 8         elif alist[mid] > item:
 9             return binary_search(alist[:mid], item)  # 在新区间内继续查找
10         else:
11             return binary_search(alist[mid+1:], item)  # 在新区间内继续查找
12     return False  # 没有查到元素

1.2.非递归形式

 1 def binary_search(alist, item):
 2     """二分查找---非递归版本"""
 3     n = len(alist)
 4     left, right = 0, n-1
 5     while left <= right:  # 查找控制
 6         mid = left + ((right - left) >> 2)  # >>的优先级比较低
 7         if alist[mid] == item:
 8             return True
 9         elif alist[mid] > item:
10             right = mid - 1
11         else:
12             left = mid + 1
13     return False

2.二分查找法的变体

2.1.查找第一个值等于给定值的元素

# 在a[mid] = item的情况下：

# 若mid=0，该元素已经是数组的第一个元素，那它肯定是我们要找的；

# 若mid!=0，但a[mid]的前一个元素a[mid-1]!=item，则a[mid]就是要找的第一个等于给定值的元素；

# 若mid!=0，且a[mid]前面的一个元素[mid-1]也等于item，则此时的a[mid]不是第一个等于给定值的元素，第一个值还在它前面；

 1 def binary_search(alist, item):
 2     """二分查找---变体"""
 3     n = len(alist)
 4     left, right = 0, n-1
 5     while left <= right:  # 查找控制
 6         mid = left + ((right - left) >> 2)  # >>的优先级比较低
 7         if alist[mid] > item:
 8             right = mid - 1
 9         elif alist[mid] < item:
10             left = mid + 1
11         else: 
12             if mid == 0 or alist[mid-1] != item:
13                 return mid
14             else:
15                 right = mid - 1
16     return False

2.2.查找最后一个值等于给定值的元素

# 在a[mid] = item的情况下：

# 若mid=n-1，该元素已经是数组的最后一个元素，那它肯定是我们要找的；

# 若mid!=0，但a[mid]的后一个元素a[mid+1]!=item，则a[mid]就是要找的最后一个等于给定值的元素；

# 若mid!=0，且a[mid]后面的一个元素a[mid+1]也等于item，则此时的a[mid]不是最后一个等于给定值的元素，最后一个值还在它后面；

 1 def binary_search(alist, item):
 2     """二分查找---变体"""
 3     n = len(alist)
 4     left, right = 0, n-1
 5     while left <= right:  # 查找控制
 6         mid = left + ((right - left) >> 2)  # >>的优先级比较低
 7         if alist[mid] > item:
 8             right = mid - 1
 9         elif alist[mid] < item:
10             left = mid + 1
11         else:
12             if mid == n-1 or alist[mid+1] != item:
13                 return mid
14             else:
15                 left = mid + 1
16     return False

2.3.查找第一个大于等于给定值的元素

# 在a[mid] >= item的情况下：

# 若mid==0，该元素已经是数组的第一个元素，那它肯定是我们要找的；

# 若mid!=0，但a[mid]的前一个元素a[mid-1] < item，则a[mid]就是要找的第一个大于等于给定值的元素；

# 若mid!=0，且a[mid]前面的一个元素[mid-1]也大于等于item，则此时的a[mid]不是第一个大于等于给定的元素，第一个值还在它前面；

 1 def binary_search(alist, item):
 2     """二分查找---变体"""
 3     n = len(alist)
 4     left, right = 0, n-1
 5     while left <= right:  # 查找控制
 6         mid = left + ((right - left) >> 2)  # >>的优先级比较低
 7         if alist[mid] >= item:
 8             if mid == 0 or alist[mid-1] < item:
 9                 return mid
10             else:
11                 right = mid - 1
12         else:
13             left = mid + 1
14     return False

2.4.查找最后一个小于等于给定值的元素

# 在a[mid] <= item的情况下：

# 若mid==n-1，该元素已经是数组的最后一个元素，那它肯定是我们要找的；

# 若mid!=0，但a[mid]的后一个元素a[mid+1] > item，则a[mid]就是要找的最后一个小于等于给定值的元素；

# 若mid!=0，且a[mid]后面的一个元素[mid+1]也小于等于item，则此时的a[mid]不是最后一个小于等于给定的元素，第一个值还在它后面；

 1 def binary_search(alist, item):
 2     """二分查找---变体"""
 3     n = len(alist)
 4     left, right = 0, n-1
 5     while left <= right:  # 查找控制
 6         mid = left + ((right - left) >> 2)  # >>的优先级比较低
 7         if alist[mid] <= item:
 8             if mid == n-1 or alist[mid+1] > item:
 9                 return mid
10             else:
11                 left = mid + 1
12         else:
13             right = mid - 1
14     return False