动画：面试官问我如何在 20 万 IP 地址中快速定位某一归属地？(下)

写在前边

上回讲到，如何在 1 亿数据中查找一个整数，重新认识了二分查找，二分查找的适用条件以及手写代码时应该注意到的细节问题。

动画：面试官问我如何在 1 亿数据中快速查找某一整数？(上)

上节只不过是一个实现一个最简单的二分查找，也是对二分查找的一个初步的认识，还记得我们在文章末尾留了一个小问题吗？在实际开发中，我们所有的数据不可能都是有序的，而且还存在重复的数据，那如何怎么实现查找呢？

这个问题又受到面试官的喜欢，面试官继续问你，给你 20 万的 IP 地址，怎么快速定位一个给定的 IP 地址呢？因为 IP 都是有一定范围的，查找某一指定 IP 地址，需要先确定范围之后，再具体找出 IP 地址。如下：

1[101.110.134.0, 101.110.134.245]  山东潍坊 2[101.110.135.0, 101.110.135.245]  山东枣庄3[101.110.155.34, 101.110.157.245] 山东菏泽4[101.110.46.0, 101.110.48.245]    山东日照

所以这篇文章就会讲到二分查找的扩展使用，在重复的数据中怎么去做查找。

对于一组重复的数据中查找数据，找一个具体的数可能存在重复的值，那到底查找哪一个算是找到了，能不能说的再具体一点？比如，我们在一组数据中查找一个数，如果有重复数据，我们就返回该重复元素的第一个元素或者最后一个元素。

比如。我们在下图中查找 4 ，图中有两个 4，我们要么返回第一个元素 4，要么就返回第二个元素 4，具体看要求是什么？

又比如，查找第一个元素符合大于或者小于指定某一指定元素的数据。比如我们第一个查找等于或小于 57 的元素。

通过下图，我们很容易找到满足条件的元素是 56，如果我们用二分查找，应该怎么改进呢？

我们将上边的分为两大情况和四小部进行具体分析思路。

思维导图

查找重复数据的第一个元素

如果我们有一组数据（含有重复的），如下：

如何使用二分查找查找出给定整数在这组数据中的下标，如果我们使用上一篇文章的做法，如果出现重复的数据，就不适用了，因为我们要查找的是，如果该元素是重复的数据，我们要返回重复数据的第一个元素。

其实也是二分查找的思路，只不过是稍微修改一下二分查找。我们仔细观察上述一组数据的特点，重复数据的第一个元素有什么特点呢？

第一种情况：

假如我们二分查找的不是第一个元素，我们就判断，该元素的前一个元素是否和自身相同，如果相同，则说明当前的元素不是重复元素的第一个元素，而是继续往前移动一个元素，继续判断。如果前一个元素和自身不相同，则当前元素是重复元素的第一个元素。

第二种情况：

还有一种情况就是如果查找的元素是所有数据的第一个元素，它没有前一个元素，那么当前元素就是我们要查找的元素。

动画实现：

代码实现：

avaScript 版本

J
Java 版本

查找重复数据的最后一个元素

重复数据的最后一个元素，和上边同一个原理的，需要判断当前元素的后一个元素是否相同，如果相同则当前元素不是最后一个元素。同样的，如果当前元素为最后一个元素，后一个没有数据，那么当前元素就是我们要查找的元素。

比如我们查找上述元素中重复元素中最后一个 4。

动画实现：

代码实现

JavaScript 版本

Java 版本

查找第一个小于等于指定的元素

给定一组数据，如下：

我们查找第一个小于等于 11 的元素下标，首先我们通过二分查找找到中间数据 6， 6 < 11，然后判断 6 后边的紧接着的数据 8 是否大于 11，如果大于 11 的话，就说明 6 就是当前小于等于指定元素的数据了。

但是 8 并不大于 11，所以减少区间，继续查找，我们再取中间数据 10，然后 10 是小于 11 的，所以判断 10 后边的元素是否大于 11, 10 后边是 21 的确大于 11，所以我们就认为 10 就是我们要找的第一个小于等于 11 的元素，查找完毕。

有种特殊情况就是，如果我们查找第一个小于等于 22 的数据，查找到 21 了，因为 21 的后方没有数据，所以认定 21 就是我们查找的第一个小于等于 22 的数据了，毕竟二分查找的前提数据是有顺序的（从小到大）。

动画实现：

代码实现：

JavaScript 版本

Java 版本

查找第一个大于等于指定的元素

查找第一个大于等于指定的元素，正好和上述的相反，通过对二分查找找到的元素进行判断，当前元素是否大于要查找的第一个大于等于的元素，如果大于，判断前一个元素是否小于查找的元素，如果小于，则当前元素就是我们要查找的元素。

比如，我们还是上述的数据，查找第一个大于等于 5 的元素。

动画实现：

代码实现：

JavaScript 版本

Java 版本

小结

回答最初的问题，给你 20 万的 IP 地址数据，如果快速定位某一指定的 IP 地址呢？我们知道， IP 地址都是分范围的，某一范围属于哪个省或者市，要想定位某一 IP 地址，首先要定位到某个城市范围的 IP 地址中去，我们知道所有范围的 IP 地址的最大值和最小值。

更多相关文章

随机推荐