二分查找的次数

前端精髓

共 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,需要依次比较

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

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

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


浏览 42
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报