二分查找_设某个有序表中有8个元素,使用二分法查找到其中某一个元素需多少次?

作者：我家小花儿 | 2024-05-26 01:07:06

踩

设某个有序表中有8个元素,使用二分法查找到其中某一个元素需多少次?

已知有16个元素的有序数组：

1 3 5 8 12 13 15 16 20 25 38 49 57 61 75 82 十六个元素的有序数组

举最坏的例子，比如想要找出数字13

开始找中间的元素作为中心点，长度的一半：

一、分析13是小于中心点16的，所以不考虑数组的后一半，而考虑数组的前一半

1 3 5 8 12 13 15 16 总长度的一半:16 * (1/2) = 8

二、然后再进行折半查找，8 (1/ 2) = 4

中心点是8,8是小于13的，所以选择中心点后面的一半数据：12 13 15 16

三、以此类推：每次都是寻找子数组的中间元素:

12 13 中心点：4 (1/2) = 2; 是13，取左边一半数据 12 13

四、再进行折半查找，2 (1/2) = 1 是13

每次和和中间元素比较都会使搜索范围减半；

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/624472