12 二分查找

宋涛收录于 Python

2018-10-19 约 1633 字预计阅读 4 分钟

不简单的简单二分查找

1. 特性

二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找看似简单，但是二分查找的变体一点都不简单，“你”经常看到的二分查找其实是最简单的二分查找即: 有序数组中不存在重复元素，通过二分查找值等于给定值的数据。注意不重复和等于，这里存在很多的变体。

其次二分查找存在很大的局限性:

二分查找依赖的是顺序表结构，简单点说就是数组。

主要原因是二分查找算法需要按照下标随机访问元素。数组按照下标随机访问数据的时间复杂度是 O(1)
如果是链表，随机访问的时间复杂度是 O(n)。如果数据使用链表存储，二分查找的时间复杂就会变得很高。
其他数据结构存储的数据，则无法应用二分查找。

二分查找针对的是有序数据。如果数据没有序，就要先排序。

所以，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中
针对频繁插入删除的动态数据集合二分查找将不再适，快速查找需要使用二叉树

数据量太大不适合二分查找: 二分查找依赖数组，而数组为了支持随机访问，需要连续的内存空间，对内存的要求苛刻。

要注意数组要求的连续内存意味着即便系统上有零散的 2G 内存也无法申请到连续的 1G 内存。虽然数组对内存要求苛刻，但是同等条件下数组却是最省内存空间的存储方式，因为除了数据本身之外，不需要额外存储其他信息。

1.1 二分查找的变形

如果放开不重复和等于的限制，二分查找有很多变形，典型的包括:

查找第一个值等于给定值的元素
查找最后一个值等于给定值的元素
查找第一个大于等于给定值的元素
查找最后一个小于等于给定值的元素

凡是用二分查找能解决的，绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省，但是毕竟内存如此紧缺的情况并不多。实际上，“值等于给定值”的二分查找确实不怎么会被用到，二分查找更适合用在“近似”查找问题，在这类问题上，二分查找的优势更加明显。比如今天讲的这几种变体问题，用其他数据结构，比如散列表、二叉树，就比较难实现了。

2. 实现

2.1 最简单的二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12



def binary_search(A, value):
  start  = 0
  end = len(A) - 1
  while start <= end:
    mid = start + ((end -start) >> 1)
    if A[mid] == value:
      return mid
    elif A[mid] < value:
      start = mid + 1
    else:
      end = mid -1

最简单的二分查找实现中有以下几个需要注意的点:

循环退出条件是 start <= end 不是 start < end
使用 mid=(low+high)/2 对mid取值是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
start 和 end 的更新，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致死循环。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def bs_first(A, value):
  start = 0
  n = end = len(A) - 1
  while start <= end:
    mid = start + ((end - start) >> 1)
    if A[mid] < value:
      start = mid + 1
    elif A[mid] > value:
      end = mid - 1
    else:
      # 判断当前 mid 是否为第一个出现的值
      if mid == 0 or (A[mid-1] != value): return mid
      end = mid - 1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


def bs_end(A, value):
  start = 0
  n = end = len(A) - 1
  while start <= end:
    mid = start + ((end - start) >> 1)
    if A[mid] < value:
      start = mid + 1
    elif A[mid] > value:
      end = mid - 1
    else:
      # 判断当前 mid 是否为最后一个出现的值
      if mid == n or (A[mid + 1] != value): return mid
      end = mid + 1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def bs_gte_first(A, value):
  start = 0
  n = end = len(A) - 1
  while start <= end:
    mid = start + ((end - start) >> 1)
    if A[mid] >= value:
      # 判断是否为第一个
      if mid == 0 or (A[mid - 1] < value): return mid
      end = mid - 1
    else:
      start  = mid + 1

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


def bs_lte_end(A, value):
  start = 0
  n = end = len(A) - 1
  while start <= end:
    mid = start + ((end - start) >> 1)
    if A[mid] > value:
      end = mid -1
    else:
      # 判断是否为最后一个
      if mid == n or (A[mid + 1] > value): return mid
      start = mid + 1

参考:

目录