数据结构与算法之美学习笔记:16 | 二分查找(下):如何快速定位IP对应的省份地址?

目录

  • 前言
  • 二分查找的变形问题
    • 变体一:查找第一个值等于给定值的元素
    • 变体二:查找最后一个值等于给定值的元素
    • 变体三:查找第一个大于等于给定值的元素
    • 变体四:查找最后一个小于等于给定值的元素
  • 解答开篇
  • 内容小结

前言

在这里插入图片描述
本节课程思维导图:
在这里插入图片描述
抛出问题:假设我们有 12 万条这样的 IP 区间与归属地的对应关系,如何快速定位出一个 IP 地址的归属地呢?

二分查找的变形问题

二分查找的变形问题很多,我只选择几个典型的来讲解,其他的你可以借助我今天讲的思路自己来分析。
在这里插入图片描述

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

如果我们在有序数据集合中存在重复的数据,我们希望找到第一个值等于给定值的数据,这样之前的二分查找代码还能继续工作吗?
比如下面这样一个有序数组,其中,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 的元素,因为第一个值等于 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 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 的大小关系有三种情况:大于、小于、等于。对于 a[mid]>value 的情况,我们需要更新 high= mid-1;对于 a[mid]<value的情况,我们需要更新 low=mid+1。那当 a[mid]=value 的时候应该如何处理呢?
如果我们求解的是第一个值等于给定值的元素,当 a[mid]等于要查找的值时,我们就需要确认一下这个 a[mid]是不是第一个值等于给定值的元素。如果 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]之间。

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

前面的问题是查找第一个值等于给定值的元素,我现在把问题稍微改一下,查找最后一个值等于给定值的元素,又该如何做呢?
具体代码:

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]这个元素已经是数组中的最后一个元素了,那它肯定是我们要找的;如果 a[mid]的后一个元素 a[mid+1]不等于 value,那也说明 a[mid]就是我们要找的最后一个值等于给定值的元素。如果我们经过检查之后,发现 a[mid]后面的一个元素 a[mid+1]也等于 value,那说明当前的这个 a[mid]并不是最后一个值等于给定值的元素。我们就更新 low=mid+1,因为要找的元素肯定出现在[mid+1, high]之间。

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

现在我们再来看另外一类变形问题。在有序数组中,查找第一个大于等于给定值的元素。比如,数组中存储的这样一个序列: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,那要查找的值肯定在[mid+1, high]之间,所以,我们更新 low=mid+1。
对于 a[mid]大于等于给定值 value 的情况,我们要先看下这个 a[mid]是不是我们要找的第一个值大于等于给定值的元素。如果 a[mid]前面已经没有元素,或者前面一个元素小于要查找的值 value,那 a[mid]就是我们要找的元素。如果 a[mid-1]也大于等于要查找的值 value,那说明要查找的元素在[low, mid-1]之间,所以,我们将 high 更新为 mid-1。

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

现在,我们来看最后一种二分查找的变形问题,查找最后一个小于等于给定值的元素。比如,数组中存储了这样一组数据: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;
}

解答开篇

好了,现在我们回头来看开篇的问题:如何快速定位出一个 IP 地址的归属地?
现在这个问题应该很简单了。如果 IP 区间与归属地的对应关系不经常更新,我们可以先预处理这 12 万条数据,让其按照起始 IP 从小到大排序。如何来排序呢?我们知道,IP 地址可以转化为 32 位的整型数。所以,我们可以将起始地址,按照对应的整型值的大小关系,从小到大进行排序。
然后,这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中,查找最后一个小于等于某个给定值的元素”了。
当我们要查询某个 IP 归属地时,我们可以先通过二分查找,找到最后一个起始 IP 小于等于这个 IP 的 IP 区间,然后,检查这个 IP 是否在这个 IP 区间内,如果在,我们就取出对应的归属地显示;如果不在,就返回未查找到。

内容小结

凡是用二分查找能解决的,绝大部分我们更倾向于用散列表或者二叉查找树。即便是二分查找在内存使用上更节省,但是毕竟内存如此紧缺的情况并不多。
“值等于给定值”的二分查找确实不怎么会被用到,二分查找更适合用在“近似”查找问题,在这类问题上,二分查找的优势更加明显。用其他数据结构,比如散列表、二叉树,就比较难实现了。
变体的二分查找算法容易出错的细节有:终止条件、区间上下界更新方法、返回值选择。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/121935.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

第三章:人工智能深度学习教程-人工智能与机器学习与深度学习之间的区别

人工智能基本上是通过一组规则&#xff08;算法&#xff09;将人类智能融入机器的机制。人工智能是两个词的组合&#xff1a;“人工”是指由人类或非自然物体制造的东西&#xff0c;“智能”是指相应地理解或思考的能力。另一个定义可能是“人工智能基本上是训练机器&#xff0…

KeyShot for 3dMax插件教程

KeyShot for 3dMax插件教程 KeyShot是一款先进的3D渲染和动画软件&#xff0c;通过直观、精简的用户界面和革命性的动画工作流简化了整个媒体创建过程&#xff0c;可以实时创建完全渲染的动画。 快速 立即查看结果。 这就是KeyShot渲染引擎的功能&#xff1a;您所做的每一个更…

鸿蒙原生应用开发-DevEco Studio远程真机的使用

一、先看看远程真机支持的机型情况相比本地和模拟器多了很多机型 二、远程真机使用的相关说明 该特性在DevEco Studio V2.2 Beta1及更高版本中支持。 如果开发者没有真机设备资源&#xff0c;则不能很方便的调试和验证HarmonyOS应用&#xff0c;为方便开发者&#xff0c;De…

U-Mail邮件系统安全登录解决方案

企业邮箱是企业对内对外商务往来的主要通信工具&#xff0c;并且企业邮箱里面还包含了大量企业内部隐私信息、商业机密等&#xff0c;很容易成为黑客的攻击目标。其中邮件盗号是企业邮箱遭受攻击的主要形式&#xff0c;一旦企业邮箱密码被黑客盗取&#xff0c;黑客不仅可以利用…

中国人民大学与加拿大女王大学金融硕士——在金融领域里持续探索、成长

在金融领域里持续探索、成长&#xff0c;这是一个永无止境的旅程。在这个领域里&#xff0c;机遇与挑战并存&#xff0c;未知与已知交织&#xff0c;需要我们时刻保持敏锐的洞察力和扎实的基本功。金融市场的变化日新月异&#xff0c;我们需要时刻关注市场动态&#xff0c;了解…

Tcl语言:SDC约束命令create_generated_clock详解(下)

相关阅读 Tcl语言https://blog.csdn.net/weixin_45791458/category_12488978.html?spm1001.2014.3001.5482 设定生成时钟特性 前文的末尾提到&#xff0c;当使用-divide by或-multiply_by选项创建生成时钟时&#xff0c;会根据master clock的时钟周期派生出生成时钟的周期&am…

C++ explicit关键字的作用

explicit关键字只针带一个参数的构造函数有效 #include <iostream> using namespace std;class A { public:A(int temp) //普通构造函数{a temp;cout << "普通构造函数: a " << a << endl;}A(const A &temp) //拷贝构造函数{a temp.a…

C++对象优化

用临时对象生成新对象的时候&#xff0c;临时对象就不产生了&#xff0c;直接构造新对象

校园图书馆自习室管理系统 毕业设计源码25035

赠送源码-毕业设计&#xff1a;SSM校园图书馆自习室管理系统https://www.bilibili.com/video/BV1iN4y1k7xw/?vd_source72970c26ba7734ebd1a34aa537ef5301 SSM校园图书馆自习室座位管理系统 摘 要 21世纪时信息化的时代&#xff0c;几乎任何一个行业都离不开计算机&#xff0c;…

二十、W5100S/W5500+RP2040树莓派Pico<MQTT连接阿里云控制板载LED>

1. 前言 物联网平台提供安全可靠的设备连接通信能力&#xff0c;支持设备数据采集上云&#xff0c;规则引擎流转数据和云端数据下发设备端。此外&#xff0c;也提供方便快捷的设备管理能力&#xff0c;支持物模型定义&#xff0c;数据结构化存储&#xff0c;和远程调试、监控、…

es6过滤对象里面指定的不要的值filter过滤

//过滤出需要的值this.dataItemTypeSelectOption response.data.filter(ele > ele.dictValue tree||ele.dictValue float4);//过滤不需要的值this.dataItemTypeSelectOption response.data.filter((item) > {return item.dictValue ! "float4"&&it…

Note1: 算法的时间复杂度和空间复杂度

目录 ---前言 1.算法效率 1.1 算法的复杂度 2.时间复杂度 2.1 时间复杂度的概念 2.2 大O的渐进表示法 2.3常见时间复杂度计算举例 2.3.1 示例1 2.3.2 示例2 2.3.3 示例3 2.3.4 示例4 2.3.5 示例5 2.3.6 示例6 2.3.7 示例7 2.3.8 示例8 3.空间复杂度 3.1 示例1 …

征服地球极限,中国极地科考与登峰事业的“御寒”之旅

7日&#xff0c;全国各地大幅降温&#xff0c;今年第一场暴风雪也席卷了黑龙江。 伴随着冷空气不断入侵&#xff0c;气温持续走低&#xff0c;寒冬的脚步越来越近&#xff0c;供暖也成为了北方地区的冬季重点民生课题。 是日&#xff0c;天色未晓&#xff0c;黑龙江各地身披红…

经典OJ题:单链表的回文结构

回文结构&#xff1a; 所谓的回文结构就是将一组数值分为两个部分&#xff0c;并用取一个中间值&#xff0c;除去中间值外&#xff0c;其他的数值都是一一镜面对称相同。 如&#xff1a; 这就是单链表的回文结构 。 题目&#xff1a; 判断单链表是否符合回文结构&#xff1a;…

SOLIDWORKS参数化设计之干涉检查

SOLIDWORKS参数化设计的思路和技巧我们讲过很多了&#xff0c;今天来讲一讲如何在模型完成之后自动执行干涉检查。 SOLIDWORKS软件本身就有干涉检查的功能&#xff0c;在评估选项卡里可以找到该功能&#xff0c;我们这里说的干涉检查指的是静态干涉检查&#xff0c;即模型在静…

异常断电文件损坏docker服务异常处理

问题场景 我们在某地部署信控平台&#xff0c;当初是在产品研发早期&#xff0c;采取的还是Windows服务器部署虚拟机的方式使用virtualbox导入centos7虚拟机&#xff0c;虚拟机里运行docker服务&#xff0c;使用docker-compose统一管理客户今天上午反馈&#xff0c;昨天断电了…

【源码】自制链接表管理器

hi&#xff0c;大家好呀&#xff01; 前几天更新了个视频&#xff0c;教大家做了一个链接表的管理器&#xff0c;今天把文字内容给到大家&#xff0c;至于什么原因需要自己做一个链接表管理器&#xff0c;我在视频中有讲到&#xff0c;因为系统自带的链接表管理器没有筛选功能…

技术分享 | app自动化测试(Android)--显式等待机制

WebDriverWait类解析 WebDriverWait 用法代码 Python 版本 WebDriverWait(driver,timeout,poll_frequency0.5,ignored_exceptionsNone)参数解析&#xff1a; driver&#xff1a;WebDriver 实例对象 timeout: 最长等待时间&#xff0c;单位秒 poll_frequency: 检测的间隔步…

怎么批量获取文件名,并保存到excel?

怎么批量获取文件名&#xff1f;什么叫批量获取文件名&#xff0c;其实也非常好理解&#xff0c;就是面对大量文件是可以一次性的获取所有文件名称&#xff0c;这项技术的应用也是非常常见的&#xff0c;为什么这么说呢&#xff1f;现在很多的文档管理人员或者公司的文员&#…