二分查找法

按拼音排序的试卷如何找到嬴政的试卷我们可以先从最中间获取然后根据拼音首字母继续查找每次都获取新一轮数据的中间的值然后我们最后就可以获取到嬴政了

查找1000张试卷最坏的规模需要查找多少次

最快的查找就一次最坏的是最后才找到

论证猜想就是我们获取一个数字那么这个数除以多少次到一

一共是 k + 1 项就是 k + 1 查找

最终

  T(n) = [log2n] + 1 // 成立

  T(n) = [log2n] + 1 // 成立

如果遍历一千个学生遍历需要多少次每个人都查找一遍我们就需要一千次但是如果我们使用二分查找法那么我们只需要 100 次速度提升了一百倍

g 等于每次上一次查找的 l + r 除以 2 向下取整

把二分查找抽象成一个数组进行抽象返回 num 再 a 中的位置不存在返回 -1

function binarySearch (arr, num) {
  let l = 0; // 查询范围左边界
  let r = arr.length - 1 // 查找范围最终边界 有边界
  let guess // 默认为空

  // while 语句可以在某个条件表达式为真的前提下，
  // 循环执行指定的一段代码，直到那个表达式不为真时结束循环。

  while (l <= r) {
    guess = Math.floor((l + r) / 2)
    // 获取循环不变时
    // guess 等于l，r 中间位置

    if (arr[guess] === num) return guess
    else if (arr[guess] > num) r = guess - 1
    else l = guess + 1
    // 新的循环不变式
  }
  return -1
}

function binarySearch (arr, num) {
  let l = 0; // 查询范围左边界
  let r = arr.length - 1 // 查找范围最终边界 有边界
  let guess // 默认为空

  // while 语句可以在某个条件表达式为真的前提下，
  // 循环执行指定的一段代码，直到那个表达式不为真时结束循环。

  while (l <= r) {
    guess = Math.floor((l + r) / 2)
    // 获取循环不变时
    // guess 等于l，r 中间位置

    if (arr[guess] === num) return guess
    else if (arr[guess] > num) r = guess - 1
    else l = guess + 1
    // 新的循环不变式
  }
  return -1
}

在github 上编辑文档

二分查找法 ​

二分查找法