算法 - 二分查找_重复数据情况

上一篇讲解了二分查找的原理，并且介绍了最简单的一种二分查找的代码实现。今天我们来讲几种二分查找的变形问题。


不知道你有没有听过这样一个说法：“十个二分九个错”。二分查找虽然原理极其简单，但是想要写出没有 Bug 的二分查找并不容易。唐纳德·克努特（Donald E.Knuth）在《计算机程序设计艺术》的第 3 卷《排序和查找》中说到：“尽管第一个二分查找算法于 1946 年出现，然而第一个完全正确的二分查找算法实现直到 1962 年才出现。”


你可能会说，我们上一节学的二分查找的代码实现并不难写啊。那是因为上一节讲的只是二分查找中最简单的一种情况，在不存在重复元素的有序数组中，查找值等于给定值的元素。最简单的二分查找写起来确实不难，但是，二分查找的变形问题就没那么好写了。二分查找的变形问题很多，我只选择几个典型的来讲解，其他的你可以借助我今天讲的思路自己来分析

变体一：查找第一个值等于给定值的元素

上一节中的二分查找是最简单的一种，即有序数据集合中不存在重复的数据，我们在其中查找值等于某个给定值的数据。如果我们将这个问题稍微修改下，有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据

def binarySearch_first(array, array_size, search_value):
    """查找第一个值等于给定值的元素"""
    low = 0
    high = array_size - 1

    while low <= high:
        mid = low + ((high - low) >> 1)
        if array[mid] == search_value:
            while array[mid-1] == search_value:
                if mid - 1 == 0:
                    return 0
                mid -= 1
            return mid
        elif array[mid] < search_value:
            low = mid + 1
        else:
            high = mid - 1

这里还有一种更好的写法：

def binarySearch_first_better(array, array_size, search_value):
    """查找第一个值等于给定值的元素"""
    low = 0
    high = array_size - 1

    while low <= high:
        mid = low + ((high - low) >> 1)
        if array[mid] < search_value:
            low = mid + 1
        elif array[mid] > search_value:
            high = mid - 1
        else:
            if mid == 0 or array[mid - 1] != search_value:
                return mid
            high = mid - 1

变体二：查找最后一个值等于给定值的元素

前面的问题是查找第一个值等于给定值的元素，我现在把问题稍微改一下，查找最后一个值等于给定值的元素，又该如何做呢？

def binarySearch_last(array, array_size, search_value):
    """查找最后一个值等于给定值的元素"""
    low = 0
    high = array_size - 1

    while low <= high:
        mid = low + ((high - low) >> 1)
        if array[mid] < search_value:
            low = mid + 1
        elif array[mid] > search_value:
            high = mid - 1
        else:
            if mid == array_size-1 or array[mid + 1] != search_value:
                return mid
            low = mid + 1

变体三：查找第一个大于等于给定值的元素

现在我们再来看另外一类变形问题。在有序数组中，查找第一个大于等于给定值的元素。比如，数组中存储的这样一个序列：3，4，6，7，10。如果查找第一个大于等于 5 的元素，那就是 6。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

变体四：查找最后一个小于等于给定值的元素

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

实际上，很多人都觉得变形的二分查找很难写，主要原因是太追求第一种那样完美、简洁的写法。