二分查找

已经排序 的一打试卷找到嬴政。

查找过程：按照字母每次都一分为二

• 函数抽象

function bsearch(A, x)
A: 数组

x: 需要查找的值

返回： x在A中的位置，不存在返回 -1

g 表示猜测的位置

l 左侧边界

r 右侧边界

g = 上次 l + r 然后向上取整

function bsearch (A, x) {
  let l = 0; // 查找范围的左边界
  let r = A.length - 1; // 查找范围右边界
  let guess; // 猜测位置
  while (l <= r) {
    guess = Math.floor((l + r) / 2)
    // 循环不变式
    // guess 等于l, r中间位置
    // l：查找范围左， r: 查找范围右
    if (A[guess] === x) {
      return guess
    } else if (A[guess] > x) {
      // 猜想的值比查找的值大，说明要找的值在左边，更新右边界
      // 图查找22
      r = guess - 1
    } else {
      // 猜想的值比查找的值要小，更新做边界，在右边查找
      l = guess + 1
    }
  }
  return -1
}
const A = [3, 5, 19, 22, 25, 33, 45, 47, 57, 66, 71, 78]
console.log(bsearch(A, 88)) // -1
console.log(bsearch(A, 68)) // -1
console.log(bsearch(A, 22)) // 3

// A：数组
// x：要查找的数
// l：左边界  r 右边界
function bsearch (A, x, l = 0, r = A.length) {
  const guess = Math.floor(( l + r) / 2)
  if (l > r) {
    return -1
  }
  if (A[guess] === x) {
    return guess
  }
  return A[guess] < x ?
      bsearch(A, x, guess + 1, r)
      :
      bsearch(A, x, l, guess - 1)
}