↑↑↑ 欢迎关注，分享更多 IT 技术

注：本笔记为 公司内部技术小组持续学习 2 年多时间 + 个人整理不下 5 次的结果产出。

目录

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

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

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

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

解答开篇

小结

---

16 | 二分查找（下）：如何定位 IP 对应的省份地址？

1. 开篇题

   • 假设我们有 12 万条这样的 IP 区间与归属地的对应关系。如何快速定位出一个 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] 江苏连云港

2. 二分查找的变形问题很多，我只选择几个典型的来讲解。

   • 

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

1. 如果有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据

   • 有序数据集合如下：

   • 

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

   • 我们重点看第 11 行代码。

     1. 如果 mid 等于 0，那这个元素已经是数组的第一个元素，那它肯定就是我们要找的。

     2. 如果 mid 不等于 0

        • 但 a[mid] 的前一个元素a[mid-1] 不等于 value ，那也说明a[mid] 就是我们要找的第一个等于给定值的元素。

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

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

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

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

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

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

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

解答开篇

1. 问题： 如何快速定位出一个 IP 地址的归属地？

2. 解题方案

   • 如果 IP 区间与归属地的对应关系不经常更新

   • 我们可以先预处理这 12 万条数据，让其按照起始 IP 从小到大排序。

   • 然后，这个问题就可以转化为我们刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。

   • 我们先通过二分查找 ，找到最后一个起始 IP 小于等于这个 IP 的 IP 区间。

   • 然后，检查这个 IP 是否在这个IP 区间内

     • 如果在，我们就取出对应的归属地显示。

     • 如果不在，就返回未查到。

小结

1. 二分查找更适合用在“近似”查找问题。在这类问题上，二分查找的优势更加明显。

2. 变体的二分查找算法需要注意的细节

   • 终止条件

   • 区间上下界更新方法

   • 返回值选择

参考地址：数据结构与算法之美_算法实战_算法面试-极客时间

欢迎大家点赞、关注！！！持续分享更多 IT 技术 干货