二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//循环不变式 guess 等于l r中间位置
const bsearch = (A, x) => {
  let l = 0
  let r = A.length - 1
  let guess
  while (l <= r) {
    console.log('find')
    guess = Math.floor((l + r) / 2)
    if (A[guess] === x) return guess
    if (A[guess] > x) r = guess - 1
    else l = guess + 1
  }
  return -1
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8]
console.log(bsearch(arr, 6)) // 5