15、二分查找（上）

思考：如何用最省内存的方式实现快速查找功能？
假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，你会怎么做呢？

主要内容

核心：主要是针对有序的数据，每次用中间值来对比，将查找区间缩小一半，直到找到元素，或区间被缩小为 0。
时间复杂度推导：n、n/2、n/4、……、n/2^k，可得为 O(logn)

简单的二分查找代码

假设数据中无重复值时，简单二分查找代码如下：

循环版

function baseSearch(list) {
  let low = 0
  let high = list.length - 1

  while(low <= high) {
    const mid = (low + high) / 2
    if(list[mid]) === value) return mid
    else if(list[mid] > value) {
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  return -1
}

递归版

递推公式：find(list, s, e, value) = list[m] === value or find(list, s, m-1, value) or find(list, m+1, e, value)
终止条件：list[m] == value or s > e

function baseSearch(list, value, s = 0, e = list.length - 1) {
  if(s > e) return -1

  const mid = (s + e) / 2

  if(list[mid] === value) return mid
  else if(list[mid] > value) return baseSearch(list, value, s, mid - 1)
  else return baseSearch(list, value, mid + 1, e)
}

局限性

• 数据必须存储在顺序表(即数组)
• 数据必须是有序的
• 不适合数据规模太小，这可以直接遍历去查找
• 不适合数据规模太大，因为要求数组存储，则需要连续的存储空间，若数据量大则很难申请到数组存储空间

解答思考

思考：如何用最省内存的方式实现快速查找功能？
假设我们有 1000 万个整数数据，每个数据占 8 个字节，如何设计数据结构和算法，快速判断某个整数是否出现在这 1000 万数据中？ 我们希望这个功能不要占用太多的内存空间，最多不要超过 100MB，你会怎么做呢？

解答：使用二分查找，将数据存入数组中，1000 万 * 8 字节约等于 80 MB，然后先排序再用二分查找。
排序后可以多次使用二分查找想要的数据

内容总结

二分查找采用“二分”的逻辑，适合已排序的顺序表结构，时间复杂度为 O(logn)，即 2^32 的数据量(43 亿)也只需要 32 次就能找到

新的思考

如何编程实现“求一个数的平方根”？要求精确到小数点后 6 位

比如求 5 的平方根，x^2 = 5，求出 x
平方根计算可以使用二分查找，先设区间为(0, number)，再求中点 mid = (0+number) / 2，比较 midmid 与 number
若 number 小，则更改区间为：(0，mid)；若 number 大，则更改区间为：(mid, number)
再求中点 mid = (0+mid) / 2，继续比较 midmid 与 number

function binarySearchSqrt(num, precision = 1e-6) {
  let low = 0;
  let high = num;

  // 确保初始区间包含num的平方根
  if (num < 1) {
    high = 1;
  }

  while (high - low > precision) {
    let mid = (low + high) / 2;
    let square = mid * mid;

    if (square === num) {
        return mid.toFixed(6);  // 如果找到精确的平方根，返回结果并精确到小数点后6位
    } else if (square < num) {
        low = mid;
    } else {
        high = mid;
    }
  }

  return (low + high) / 2;  // 返回区间内的中间值作为近似解，并隐式地进行了四舍五入到小数点后6位
}

console.log(binarySearchSqrt(9));  // 输出："3.000000"
console.log(binarySearchSqrt(16));  // 输出："4.000000"
console.log(binarySearchSqrt(2));  // 输出："1.414214"