常见二分查找【变体问题】练习&解决思路

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

在不存在重复元素的有序数组中，查找值等于给定值的元素, 这是二分查找中最简单的一种情况, 实际使用过程中, 我们常常面临二分查找的变体问题。

本文主要介绍以下四种常见的二分查找变形问题。
注意: 以下二分查找的思路和代码实现都是基于数组从小到大排列的。如果是从大到小, 代码实现不同, 但思路是一样的。

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

比如下面这样一个有序数组，其中，a[5]，a[6]，a[7]的值都等于 8，是重复的数据。我们希望查找第一个等于 8 的数据，也就是下标是 5 的元素。
如果用上次的二分查找实现方式实现,
首先拿 8 与区间的中间值 a[4]比较，8 比 6 大，于是在下标 5 到 9 之间继续查找。下标 5 和 9 的中间位置是下标 7，a[7] 正好等于 8，所以代码就返回了。

尽管 a[7] 也等于 8，但是第一个值等于 8 的元素是数组下标为 5 的元素。我们通过简单的二分查找实现方式就无法处理这种情况了。所以，针对这个变形问题，我们需要稍微改造一下上一节的代码。

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) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }

  if (low < n && a[low]==value) return low;
  else return -1;
}

上面的写法虽然简洁, 但并不容易理解, 很容易写错, 而且短时间内没有办法马上写出来。实际工程开发过程中我们不必要追求极致的简洁和性能, 而是最好使用一种便于理解的实现方式。

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) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

尝试理解上面的代码实现逻辑, 主要是边界条件的处理。
如果你能直接理解上面的代码, 可以直接跳过下面的说明。

我来稍微解释一下这段代码。a[mid] 跟要查找的 value 的大小关系有三种情况：大于、小于、等于。

1. 对于 a[mid]>value 的情况，我们的目标元素肯定在二分点的左侧, 我们需要更新查找的上界: high= mid-1；
2. 对于 a[mid]

这两点都很好理解。那当 a[mid]=value 的时候应该如何处理呢？

• 如果我们查找的是任意一个值等于给定值的元素，当 a[mid]=value时，a[mid]就是我们要找的元素。但是，如果我们求解的是第一个值等于给定值的元素，当 a[mid]等于要查找的值时，我们就需要确认一下这个 a[mid]是不是第一个值等于给定值的元素。

• 我们重点看第 11 行代码。如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定是我们要找的；如果 mid 不等于 0，但 a[mid]的前一个元素 a[mid-1]不等于 value，那也说明 a[mid]就是我们要找的第一个值等于给定值的元素。

• 如果经过检查之后发现 a[mid]前面的一个元素 a[mid-1]也等于 value，那说明此时的 a[mid]肯定不是我们要查找的第一个值等于给定值的元素。那我们就更新 high=mid-1，因为要找的元素肯定出现在[low, mid-1]之间。

对比上面的两段代码，是不是下面那种更好理解？实际上，很多人都觉得变形的二分查找很难写，主要原因是太追求第一种那样完美、简洁的写法。而对于我们做工程开发的人来说，代码易读懂、没 Bug，其实更重要，所以我觉得第二种写法更好。

建议大家也尝试实现下自己的查找逻辑, 这是我的实现方式:

public int binarySearchFirstEq(int[] value, int target) {
    int low = 0;
    int high = value.length - 1;

    while (low <= high) {
        if (value[low] == target) {
            return low;
        }
        int mid = low + ((high - low) >> 1);
        if (value[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
            low++;
        }
    }
    return -1;
}

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

前面的问题是查找第一个值等于给定值的元素，我现在把问题稍微改一下，查找最后一个值等于给定值的元素，又该如何做呢？
基本思路是一致的。实现了上面的代码后, 这个问题也能很快地解决

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) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

这是我的实现方式:

public int binarySearchLastEq(int[] value, int target) {
    int low = 0;
    int high = value.length - 1;

    while (low <= high) {
        if (value[high] == target) {
            return high;
        }
        int mid = low + ((high - low) >> 1);
        if (value[mid] > target) {
            high = mid;
        } else {
            low = mid;
        }
        high--;
    }
    return -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 binarySearchLastLtEq(int[] value, int target) {
    int low = 0;
    int high = value.length - 1;

    if (value[low] > target) {
        return -1;
    }
    if (value[high] <= target) {
        return high;
    }
    while (low + 1 < high) {
        int mid = low + ((high - low) >> 1);
        if (value[mid] > target) {
            high = mid;
        } else {
            low = mid;
        }
    }
    return low;
}

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

现在，我们来看最后一种二分查找的变形问题，查找最后一个小于等于给定值的元素。比如，数组中存储了这样一组数据：3，5，6，8，9，10。最后一个小于等于 7 的元素就是 6。

其实这个问题跟上面那个问题的实现思路也是一样的。

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;
}

这是我的实现方式

public static int binarySearchFirstGtEq(int[] value, int target) {
    int low = 0;
    int high = value.length - 1;

    if (value[low] >= target) {
        return low;
    }
    if (value[high] < target) {
        return -1;
    }
    while (low + 1 < high) {
        int mid = low + ((high - low) >> 1);
        if (value[mid] < target) {
            low = mid;
        } else {
            high = mid;
        }
    }
    return high;
}

思考问题 如何快速定位出一个 IP 地址的归属地？

现在这个问题应该很简单了。如果 IP 区间与归属地的对应关系不经常更新，我们可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。如何来排序呢？我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。

然后，这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素 (归属地, IP区间上限)”了。

当我们要查询某个 IP 归属地时，我们可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间，然后，检查这个 IP 是否在这个 IP 区间内，如果在，我们就取出对应的归属地显示；如果不在，就返回未查找到。

如果有序数组是一个循环有序数组，比如 4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？ 1. 在知道偏移量即分界点的情况下, 用偏移 + 取模定位元素

int i, low = 0 + offset, high = length - 1 + offset, 对应实际下标 i % length

    public static int bsearch(int[] value, int target) {
        //如果知道偏移量的情况下, 比如offset=4
        int offset = 4;
        int length = value.length;
        int low = offset;
        int high = length - 1 + offset;
        //二分查找等于的值
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            int m = mid % length;
            if (value[m] == target) {
                return m;
            }
            if (value[m] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

2. 在不知道偏移量的情况下

循环有序数组 (4,5,6,1,2,3), 相比较有序数组 (1,2,3,4,5,6) 区别在哪里呢?

二分查找要实现O(logn)的实现复杂度, 在于每次比较二分点, 可以明确知道目标元素位于二分点的左侧或者右侧, 从而缩小查找范围。

对于有序数组, 当目标元素比二分点小时, 明确目标元素位于左侧区间, 当比二分点大时, 位于右侧。

对于循环有序数组, 当目标元素比二分点小时, 目标元素却有可能位于左侧区间, 也有可能位于右侧区间。但是比mid小的元素位于mid右侧需要满足两个条件: 1,二分点位于左边部分的数组, 2,target位于右边部分的数组。以[4,5,6,7,1,2,3]为例, mid属于4567, target属于123。比mid大同理。

这样我们就可以条件判断目标元素位于二分点的左侧 / 右侧, 从而实现二分查找。代码实现如下:

    public static int bsearch1(int[] value, int target) {

        int low = 0;
        int high = value.length - 1;
        int first = value[0];
        if(target == first){
            return 0;
        }
        while (low < high) {
            int mid = low + ((high - low) >> 1);
            if (value[mid] == target) {
                return mid;
            }
            if (value[mid] > target) {
                //因为是循环数组, 比二分点小的数, 有可能在右边
                //比二分点小的数在右边需要满足: 1,二分点位于左边部分的数组, 2,target位于右边部分的数组
                //以[4,5,6,7,1,2,3]为例, mid属于4567, target属于123
                if(value[mid] > first && target < first){
                    low = mid + 1;
                }else{
                    high = mid - 1;
                }
            } else {
                //因为是循环有序数组, 有可能在左边
                //同理, 要满足: 1,二分点位于右边部分的数组, 2,target位于左边部分的数组
                if(value[mid] < first && target > first){
                    //在左边
                    high = mid - 1;
                }else{
                    low = mid + 1;
                }
            }
        }
        if(value[low] == target) return low;
        return -1;
    }