数据结构与算法之美-二分查找

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

二分查找是针对于有序数据集合的查找算法，又称为折半查找。

1. 二分查找思想

二分查找针对的是一个有序的数据集合，每次都跟区间的中间元素做对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间变为 0。

我们需要体会的是这种二分查找思想，比如猜数字游戏，随机写一个 0 到 99 之间的数字，然后猜这个数，每猜一次都会告知是大了还是小了，直到猜中为止，假如数字为 23，猜测的步骤可能会如下所示：

image.png

可以看到 7 次就猜出来了，这个例子用的就是二分思想。

举个实际开发中的例子，假设有 10 个订单，订单金额分别是：8，11，19，23，27，33，45，55，67，98，需要找到金额为 19 元的订单。我们还是利用二分思想，每次都和区间的中间数据对比，如下图 low 和 high 表示待查找区间的下标，mid 表示待查找区间的中间元素下标：

image.png

2. 时间复杂度

假定数据大小为 n，每次查找后数据都会变为原来的一半，最坏情况下，直到查找区间被缩小为空，才停止：

image.png

这是一个等比数列。其中 n/2^k=1 时，k 的值就是总共缩小的次数，每一次缩小操作只涉及两个数据的大小比较，所以经过 k 次区间缩小操作，时间复杂度为 O(k)，通过 n/2^k = 1，得出 k = log2n，所以时间复杂度就是 O(logn)。

这种对数时间复杂度，非常高效，即使 n 非常大，对应的 logn 也很小。在常量值很大的时候，常量级的时间复杂度的算法有时候还没有 O(logn)的算法执行效率高。

3. 代码实现

3.1 非递归实现

最简单的情况就是有序数组不存在重复元素，用二分查找值等于给定值的数据，代码如下：

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;

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

  return -1;
}

这里要注意以下问题：

• 循环的条件是low<=high，而不是 low<high
• mid的取值应该写为low+(high-low)/2，如果low 和 high很大，加起来可能会溢出，除以 2 操作，可以通过位运算来完成
• low 和 high 的更新，low=mid+1，high=mid-1。如果直接写成 low=mid 或者 high=mid，可能会发生死循环

3.2 递归实现

// 二分查找的递归实现
public int bsearch(int[] a, int n, int val) {
  return bsearchInternally(a, 0, n - 1, val);
}

private int bsearchInternally(int[] a, int low, int high, int value) {
  if (low > high) return -1;

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

4. 二分查找的局限性

• 依赖顺序表结构，简单说就是数组
• 针对的是有序数据，否则就需要先排序了
• 数据量太小不适合二分查找，直接遍历就行了
• 数据量太大不适合二分查找，因为数组需要连续的内存空间，假如数据有 2GB，很恐怖。

最简单的一种二分查找的代码还是很好写的，但是实际开发中就没有这么简单了。

5. 二分查找的变形问题

image.png

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

比如下面这个有序数组，a[5] a[6] a[7] 的值都是 8，我们希望查找的是第一个值等于 8 的数据，也就是下标是 5 的元素，如下图：

image.png

如果用上次的二分查找代码实现，首先会拿 8 和区间的中间值 a[4]比较，8 比 6 大，之后再下标 5 到 9 之间继续查找，a[7]正好等于 8 ，返回下标为 7 ，但这并不是我们想要的结果啊。

修改后的代码如下：

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

这段代码有点难理解，最终目的是查找第一个值等于给定值的元素下标，所以第6行判断 a[mid] >= value，即使下标为mid的元素等于给定值，也会继续减1向左查找，如果 mid 为第一个等于给定值的元素下标，继续减 1 之后，low 也会逐步加回到这个下标。

第 13 行中 low < n 的判断，是为了防止给定值大于最后一个元素的值这种情况下的越界问题。

还有一种比较容易理解的实现方法，代码如下：

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

这个代码实现就很好理解了，在最后的 else 中此时 a[mid]的值和给定值是相等的，这里面我们做了一个判断，如果此时 mid 等于 0，或者 a[mid-1] != value，说明此时下标为 mid 的元素是第一个和给定值相等的，所以直接返回 mid，否则说明 a[mid]不是我们要查找的第一个值等于给定值的元素，那么继续更新 high = mid -1，因为要找的元素肯定出现在[low, mid-1]之间。

这两段代码都能达到我们的需求，但是第二种代码实现更容易读懂，且不容易出现 Bug，没有必要太追求完美、简洁的写法。

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

这个问题的解决思路跟上个问题相似，代码如下：

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

当 a[mid] == value时，如果a[mid]已经是数组中最后一个元素，或者 a[mid + 1] != value时，说明 a[mid]就是我们要找的最后一个值等于给定值的元素，否则就更新 low = mid + 1，因为要找的元素肯定出现在[mid + 1, high] 之间。

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

比如，这样一个数组 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;
}

对于 a[mid] >= value 的情况，如果 a[mid]已经是第一个元素，或者前面一个元素小于要查找的值 value，那么 a[mid]就是我们要找的元素，否则说明要查找的元素在[low, mid - 1] 之间，high = mid - 1。

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

比如，数组中存储了这样一组数据：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;
}

6. 如何快速定位一个 IP 地址的归属地

当我们想要查询 202.102.133.13 这个 IP 地址的归属地时，我们就在地址库中搜索，发现这个 IP 地址落在[202.102.133.0, 202.102.133.255]这个地址范围内，那我们就可以将这个 IP 地址范围对应的归属地“山东东营市”显示给用户了。

[202.102.133.0, 202.102.133.255]  山东东营市 
[202.102.135.0, 202.102.136.255]  山东烟台 
[202.102.156.34, 202.102.157.255] 山东青岛 
[202.102.48.0, 202.102.48.255] 江苏宿迁 
[202.102.49.15, 202.102.51.251] 江苏泰州 
[202.102.56.0, 202.102.56.255] 江苏连云港

在庞大的地址库中逐一比对 IP 地址所在的区间，是非常耗时的。假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？

先将 IP 从小到大排序，然后这个问题就转化成了上面在有序数组中，查找最后一个小于等于某个给定值的元素了。当要查询某个 IP 归属地时，可以先通过二分查找，找到最后一个起始 IP 小于等于这个 IP 的区间，然后检查IP 是否在 IP 区间内，如果在，就取出对应的归属地显示，否则就返回未查找到。

7. 总结

• 二分查找更适合用在“近似”查找问题
• 二分查找算法需要注意终止条件、区间上下界更新方法、返回值选择

8. 练习

• 二分查找的实现
• 求一个数的平方根？要求精确到小数点后 6 位
• 上面 4 种变种问题代码实现
• 针对于循环有序数组的二分查找