16、二分查找（下）

思考：如何快速定位 IP 对应的省份地址？
举例：查询 202.102.133.13 这个 IP 地址的归属地时，在地址库中发现这个 IP 地址落在[202.102.133.0, 202.102.133.255]这个地址范围内，就可以将这个 IP 地址范围对应的归属地显示给用户了。

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

主要内容

主要将二分的变形查找

都以数据从小到大排序为前提。

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

当数据中存在重复的值时，如何找到呢？

function bsearch(list, targetValue) {
  const len = list.length - 1
  let low = 0
  let high = len

  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const midValue = list[mid]

    if(midValue > targetValue) { // 逻辑未变
      high = mid - 1
    } else if(midValue < targetValue) { // 逻辑未变
      low = mid + 1
    } else {
      // 逻辑有变化，以前是直接 return mid

      // 当 mid 为 0，则肯定是第一个 或 前一个不等于 targetValue，则没有重复值也就是第一个
      if(mid === 0 || list[mid - 1] !== targetValue) return mid
      else high = mid - 1 // 否则前一个等于 targetValue，则要从[low, mid - 1]内再找
    }
  }

  return -1
}

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

function bsearch(list, targetValue) {
  const len = list.length - 1
  let low = 0
  let high = len

  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const midValue = list[mid]

    if(midValue > targetValue) { // 逻辑未变
      high = mid - 1
    } else if(midValue < targetValue) { // 逻辑未变
      low = mid + 1
    } else {
      // 逻辑有变化，以前是直接 return mid

      // 当 mid 为 len，则肯定是最后一个 或 后一个不等于 targetValue，则没有重复值也就是最后一个
      if(mid === len || list[mid + 1] !== targetValue) return mid
      else low = mid + 1 // 否则后一个等于 targetValue，则要从[mid + 1, high]内再找
    }
  }

  return -1
}

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

function bsearch(list, targetValue) {
  const len = list.length - 1
  let low = 0
  let high = len

  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const midValue = list[mid]

    if(midValue < targetValue) { // 逻辑未变
      low = mid + 1
    } else {
      // 大于等于的情况

      // 当 mid 为 0，则肯定是第一个 或 前一个不大于等于 targetValue，也就是第一个
      if(mid === 0 || list[mid - 1] < targetValue) return mid
      else high = mid - 1 // 否则前一个大于等于 targetValue，则要从[low, mid - 1]内再找
    }
  }

  return -1
}

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

function bsearch(list, targetValue) {
  const len = list.length - 1
  let low = 0
  let high = len

  while(low <= high) {
    const mid = Math.floor((low + high) / 2)
    const midValue = list[mid]

    if(midValue > targetValue) { // 逻辑未变
      high = mid - 1
    } else {
      // 小于等于的情况

      // 当 mid 为 len，则肯定是最后一个 或 后一个不小于等于 targetValue，也就是最后一个
      if(mid === len || list[mid + 1] > targetValue) return mid
      else low = mid + 1 // 否则后一个小于等于 targetValue，则要从[mid + 1, high]内再找
    }
  }

  return -1
}

解答思考

思考：如何快速定位 IP 对应的省份地址？
举例：查询 202.102.133.13 这个 IP 地址的归属地时，在地址库中发现这个 IP 地址落在[202.102.133.0, 202.102.133.255]这个地址范围内，就可以将这个 IP 地址范围对应的归属地显示给用户了。

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

解答：现将区间从小到大排序，可将 IP 转为 32 位整数进行排序。然后用【变体四】找到最后一个起始 IP 小于等于该 IP 的 IP 区间数据。然后检查 IP 是否在该区间内，在的话返回归属地，不在就返回未找到。

内容总结

变体的二分查找比较常用，运用的场景也多。
所以要掌握手写代码的能力

新的思考

如果有序数组是一个循环有序数组，比如 4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？

循环有序数组简单理解为环形数组，结构为 ……3,4,5,6,1,2,3,4,5……

function circularBinarySearch(list, tValue) {
  const len = list.length

  if(!len) return -1

  let start = 0
  let end = len - 1

  while(start <= end) {
    const mid = (start + end) % len // 考虑循环特性，求余来计算中间索引

    const midValue = list[mid]

    if(midValue > tValue) {
      end = mid - 1
    } else if(midValue < tValue) {
      start = mid + 1
    } else {
      return mid
    }

    if(start > end) { // 循环特性，会存在该情况
      start = start % len // 求余重置 start

      for(let i = start; i < start + end + 1; i++) {
        if(list[i % len] === tValue) return i % len
      }

      reutrn -1 // 如果整个数组遍历完都没有找到，返回 -1
    }

    reutrn -1 // 如果正常循环结束还没有找到，返回 -1
  }
}