二分查找的次数
前端精髓
共 918字,需浏览 2分钟
·
2021-08-31 09:05
折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用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次
评论