二分查找
2025-10-20 17:19:33
发布于:浙江
二分查找
假如表中元素是按升序排列
将查找范围的中间位置的值mid和目标元素x作比较,利用中间位置将表分成前和后个子表
1.如果查找范围的中间值==目标元素,则查找成功;
2.如果目标元素<查找范围的中间值,则查找范围缩小到前一子表;
3.如果查找范围的中间值<目标元素;则查找范围缩小到前一子表;
重复以上过程,直到找到目标元素,则查找成功,
或者直到子表不存在为止,此时则查找不成功。
思路二. 每次猜中间,查找范围减半,直至猜中为止。
二分查找 时间复杂
求n个有序的数 二分查找的时间复杂度:
看n除以多少次2为0
即看n 除以多少次2为0
为 log2n向下取整+1
时间复杂度1次可以忽略,所以
二分查找的时间复杂度:log2n
这里空空如也









有帮助,赞一个