二分法查找

背景

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

  介绍

• 二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

• 二分查找是时间复杂度为 O(logn) 的算法

  应用场景（局限性）

• 首先，二分查找依赖的是顺序表结构，简单点说就是数组。

• 其次，二分查找针对的是有序数据。
• 再次，数据量太小不适合二分查找。

  代码实现（简单二分法查找）

  有序数组中不存在重复元素

  ```javascript // 循环实现 const bsearch = (arr = [], value) => { const len = arr.length if (len === 0) return -1 let low = 0 let height = len - 1 while (low <= height) { let mid = Math.floor((height + low) / 2) if (value === arr[mid]) {

  return mid

  } else if (value < arr[mid]) {

  // 在左半区间
  height = mid - 1

  } else {

  // 在右半区间
  low = mid + 1

  } } return -1 }

// 递归实现 const len = arr.length if (len === 0) return -1 return bsearchInter(arr, 0, len - 1, value) }

const bsearchInter = (arr, low, height, value) => { if(low > height) return -1 let mid = Math.floor((height + low) / 2) if (arr[mid] === value) { return mid } else if (value < arr[mid]) { return bsearchInter(arr, low, mid -1, value) } else { return bsearchInter(arr, mid + 1, height -1, value) } }

- 循环退出条件注意是 low<=high，而不是 low<high。
- mid 的取值实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多。
- low 和 high 的更新low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。比如，当 high=3，low=3 时，如果 a[3]不等于 value，就会导致一直循环不退出。
<a name="A1XdV"></a>
#### 题目
- 如何编程实现“求一个数的平方根”？要求精确到小数点后 6 位。
<a name="eKYeC"></a>
### 二分法查找变形问题
<a name="lHmrk"></a>
## ![image.png](https://cdn.nlark.com/yuque/0/2021/png/12492651/1624199217340-3acc2328-6516-4e61-923b-e51e3a4004b5.png#clientId=u1324d288-2ad6-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=357&id=ufa91e5ee&margin=%5Bobject%20Object%5D&name=image.png&originHeight=714&originWidth=1076&originalType=binary&ratio=2&rotation=0&showTitle=false&size=720476&status=done&style=none&taskId=ud5bf7d70-3f9c-44f6-8adc-84b22319c97&title=&width=538)
<a name="j0rr5"></a>
#### 查找第一个值等于给定值的元素
- 有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据
- 比如下面这样一个有序数组，其中，a[5]，a[6]，a[7]的值都等于 8，是重复的数据。我们希望查找第一个等于 8 的数据，也就是下标是 5 的元素。
![image.png](https://cdn.nlark.com/yuque/0/2021/png/12492651/1624199442648-ff3ba752-ac95-4b5e-9408-4052cb6060d0.png#clientId=u1324d288-2ad6-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=134&id=u5e6a8a1f&margin=%5Bobject%20Object%5D&name=image.png&originHeight=268&originWidth=1088&originalType=binary&ratio=2&rotation=0&showTitle=false&size=137211&status=done&style=none&taskId=u5abaf958-a591-4acf-8236-575a424b904&title=&width=544)
```javascript
const arr = [1,2,3,3,3,3,4]
const bsearch = (arr = [], value) => {
  const len = arr.length
  if (len === 0) return -1
  let low = 0
  let height = len - 1
  while (low <= height) {
    let mid = Math.floor((height + low) / 2)
    if (arr[mid] < value) {
      // 右区间
      low = mid + 1
    } else if (arr[mid] > value) {
      // 左区间
      height = mid - 1
    } else {
      // 这里肯定找到元素了，判断它前一个元素值和给定值 value 是否相等即可
      // 第一个元素 mid === 0
      // 前一个元素值和给定值 value 是否相等
      if (mid === 0 || arr[mid - 1] !== value) {
        return mid
      }
      // 如果 前一个元素 arr[mid - 1 === value
      // 再次 二分
      height = mid - 1
    }
  }
  return -1
}

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

const arr = [1,2,3,3,3,3,4]
const bsearch = (arr = [], value) => {
  const len = arr.length
  if (len === 0) return -1
  let low = 0
  let height = len - 1
  while (low <= height) {
    let mid = Math.floor((height + low) / 2)
    if (arr[mid] < value) {
      // 右区间
      low = mid + 1
    } else if (arr[mid] > value) {
      // 左区间
      height = mid - 1
    } else {
      // 这里肯定找到元素了，判断它后一个元素值和给定值 value 是否相等即可
      // 第一个元素 mid === 0
      // 前一个元素值和给定值 value 是否相等
      if (arr[mid + 1] !== value) {
        return mid
      }
      // 如果 后一个元素 arr[mid + 1] === value
      // 再次 二分
      low = mid + 1
    }
  }
  return -1
}

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

const bsearch = (arr = [], value) => {
  const len = arr.length
  if (len === 0) return -1
  let low = 0
  let height = len - 1
  while (low <= height) {
    let mid = Math.floor((height + low) / 2)
    if (arr[mid] >= value) {
      // 判断是不是第一个元素就好
      if((mid === 0) || arr[mid - 1] < value) {
        return mid
      } else {
        height = mid - 1
      }
    } else {
      low = mid + 1
    }
  }
  return -1
}

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

const bsearch = (arr = [], value) => {
  const len = arr.length
  if (len === 0) return -1
  let low = 0
  let height = len - 1
  while (low <= height) {
    let mid = Math.floor((height + low) / 2)
    if (arr[mid] > value) {
      height = mid - 1
    } else { // 小于等于 情况
      // 判断后一个元素是否大于 value
      // mid === len 最后一个元素
      if (mid == len || arr[mid + 1] > value) {
        return mid
      } else {
        low = mid + 1
      }
    }
  }
  return -1
}

题目

—假设我们有 12 万条这样的 IP 区间与归属地的对应关系，如何快速定位出一个 IP 地址的归属地呢？

• 将12万条32位IP地址转为整型
• 让其按照起始 IP 从小到大排序
• 查找最后一个小于等于给定值的元素

比如：假设坐标区间是0-5 10-15 20-25 30-35 查找的坐标是22，

1. 将坐标区间起始数字组成数组 (0 10 20 30)
2. 查找最后一个小于22的起始区间20 看22在不在20-25的区间内， 在的话返回地址，不在返回没有查询到

代码实现

• 32位IP地址转为整型

>> 位操作
32位IP地址转为整型
正则验证IP

• 2(5[0-5]|[0-4]\d) 匹配：200 ~ 255
• [0-1]?\d{1,2} 匹配：0 ~ 199
• 0 到 255 的式子已经写出来了，那么一共四段再加上中间的点就很容易了

  后边“点”和“数字”重复三次就可以了
  (\.((2(5[0-5]|[0-4]\d))|[0-1]?\d{1,2})){3}

  // 利用位操作
  // 注意： parseInt(result[4]))>>>0;无符号右移0位
  function ipToInt(IP){
  const REG =/^(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])\.(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])\.(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])\.(\d{1,2}|1\d\d|2[0-4]\d|25[0-5])$/;
  const reg = /[0-1]?\d{1,2}|2([0-4]\d|5[0-5])(\.((2(5[0-5]|[0-4]\d))|[0-1]?\d{1,2})){3}/
  const pattern = /((2(5[0-5]|[0-4]\d))|[0-1]?\d{1,2})(\.((2(5[0-5]|[0-4]\d))|[0-1]?\d{1,2})){3}/g,
  var xH = "",result = reg.exec(IP);
  if(!result) return -1;
  return (parseInt(result[1]) << 24 
      | parseInt(result[2]) << 16
      | parseInt(result[3]) << 8
      | parseInt(result[4]))>>>0;
  }