二分查找的次数

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用O(log n)完成搜索任务。它的基本思想如下：

const arr = [12,24,36,48,60,72,84]
const target = 72

function  find (arr, target) {
  let left = 0
  let right = arr.length - 1
  while (left <= right) {
    let mid = (left + right) >> 1
    let cur = arr[mid]
    if (cur === target) {
      return mid
    } else if (cur < target) {
      left = mid + 1
    } else {
      right = mid - 1
    }
  }
}

console.log(find(arr, target))

第1题

二分查找有序列表

[2,10,25,35,40,65,70,73,75,81,82,88,100]

如果查找元素75，需要依次比较

70
81
73
75

(0+12)/2 索引6 第1次
(7+12)/2 索引9 第2次
(7+8)/2  索引7 第3次
(8+8)/2  索引8 第4次

第2题

二分查找有序列表

[1,2,3,4,5,6,7,8,9,10,11,12,13,14]

如果查找元素4，需要依次比较

7
3
5
4

(0+13)/2 索引6 第1次
(0+5)/2  索引2 第2次
(3+5)/2  索引4 第3次
(3+3)/2  索引3 第4次

第3题

二分查找有序列表

[12,24,36,48,60,72,84]

如果查找72那么需要比较2次

48
72

(0+6)/2  索引3 第1次
(4+6)/2  索引5 第2次