如何用最省内存的方式实现快速查找功能

假设有1000万个整数数据，每个数据占8个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这100万数据中？

二分查找思想

一组有序数字，猜数字
每次取中间的数字做对比，缩小查找区间的范围。
image.png
二分查找针对的是有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0.
**
二分法的时间复杂度为O(logn)

二分查找法递归与非递归实现

简单的二分查找算法

  1. function bSearch (arry, target) {
  2.   if (arry.length === 0) return -1
  4.   let low = 0
  5.   let hight = arry.length - 1
  7.   while (low <= hight) {
  8.     let mid = Math.floor((low + hight) / 2)
  9.     if (arry[mid] === target) {
  10.       return mid
  11.     } else if (arry[mid] > target) {
  12.       hight = mid - 1
  13.     } else if (arry[mid] < target) {
  14.       low = mid + 1
  15.     }
  16.   }
  17.   return -1
  18. }

注意：

  1. 循环退出条件，是low<=hight
  2. mid的取值，注意溢出，取中间值

  3. low和high的更新需要注意加减1

    二分查找应用的局限性

  4. 二分查找依赖的是顺序表结构，数组。二分查找按照下标随机访问元素。

  5. 二分查找针对的是有序数据。
  6. 数据量太小不适合二分查找。只有数据量比较大的时候才适合用二分查找
  7. 数据量太大也不适合二分查找。二分查找依赖数组这种数据结构，要求内存空间连续，对内存要求比较苛刻。

解答提问小结

如何在1000万个整数中快速查找某个整数？
先对1000万个数据进行排序，然后使用二分法查找。
二分查找，除了数据本身之外，不需要额外存储其他信息，是最省内存空间的存储方式。

二分法的中心思想是每次从数据的中间取一个数据与目标值进行比较，缩小范围。
局限性就是对数据要求严格，必须有序的数组。
更适合处理静态数据，也就是没有频繁的数据插入、删除操作。

如何快速定位IP对应的省份地址

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

二分查找变形

image.png

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

image.png
比如这个数组，有三个重复的8，希望查找第一个等于8的数据。
如果按照正常的二分法查找，找到等于8的数据就返回了，并不会返回第一个等于8的数据的位置。

  1. function bSearch (arry, target) {
  2.   if (arry.length === 0) return -1
  4.   let low = 0
  5.   let hight = arry.length - 1
  7.   while (low <= hight) {
  8.     let mid = Math.floor((low + hight) / 2)
  9.     if (arry[mid] > target) {
  10.       hight = mid - 1
  11.     } else if (arry[mid] < target) {
  12.       low = mid + 1
  13.     } else {
  14.       if ((mid === 0) || (a[mid -1] !== target)) {
  15.         return mid
  16.       } else {
  17.         hight = mid - 1
  18.       }
  19.     }
  20.   }
  21.   return -1
  22. }

如果有重复的元素数组，我们需要确定这是不是我们要找的第一个元素，第十四行，要判断前一个数是否是和目标值相等，如果不相等，mid就是我们要找的数，如果相等，需要在low 和 mid - 1 区间继续寻找下去，直到找到第一个数。

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

  1. function bSearch (arry, target) {
  2.   if (arry.length === 0) return -1
  4.   let low = 0
  5.   let hight = arry.length - 1
  6.   let len = arry.length
  8.   while (low <= hight) {
  9.     let mid = Math.floor((low + hight) / 2)
  10.     if (arry[mid] > target) {
  11.       hight = mid - 1
  12.     } else if (arry[mid] < target) {
  13.       low = mid + 1
  14.     } else {
  15.       if ((mid === len - 1) || (a[mid + 1] !== target)) {
  16.         return mid
  17.       } else {
  18.         low = mid + 1
  19.       }
  20.     }
  21.   }
  22.   return -1
  23. }

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

  1. function bSearch (arry, target) {
  2.   if (arry.length === 0) return -1
  4.   let len = arry.length
  5.   let low = 0
  6.   let hight = len - 1
  8.   while (low <= hight) {
  9.     let mid = Math.floor((low + hight) / 2)
  10.     if (arry[mid] >= target) {
  11.       if ((mid === 0) || (arry[mid -1] < target)) {
  12.         return mid
  13.       } else {
  14.         hight = mid - 1
  15.       }
  16.     } else if (arry[mid] < target) {
  17.       low = mid + 1
  18.     }
  19.   }
  20.   return -1
  21. }

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

  1. function bSearch (arry, target) {
  2.   if (arry.length === 0) return -1
  4.   let len = arry.length
  5.   let low = 0
  6.   let hight = len - 1
  8.   while (low <= hight) {
  9.     let mid = Math.floor((low + hight) / 2)
  10.     if (arry[mid] > target) {
  11.       hight = mid - 1
  12.     } else if (arry[mid] < target) {
  13.       if ((mid === len - 1) || (arry[mid + 1] > target)) {
  14.         return mid
  15.       } else {
  16.         low = mid + 1
  17.       }
  18.     }
  19.   }
  20.   return -1
  21. }

这四种变形，主要是数组中的数据不同引起的，关键在于边界条件的判断，主要思路还是二分查找法。

解答与小结

查找对应的IP归属地。
可以先对IP区间归属地进行排序，将起始地址，按照对应的整型值的大小关系，进行排序。
然后可以将问题转化为，查找最后一个小于等于给定值的元素。
找到最后一个起始IP小于等于这个IP的IP区间，然后检查这个IP是否在这个区间。

凡是用二分法查找能解决的，绝大部分我们更倾向于散列表或者二叉树查找

二分查找更适合用在”近似”查找问题上，这类问题，二分查找很有优势。
注意变体查找容易出错的细节：终止条件、区间上下界更新方法、返回值选择。