二分查找的次数-轻识

折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用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，需要依次比较

70817375

(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，需要依次比较

(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次

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