1.2二分法

二分法查找

适用场景:在已经排序好的数据里,如顺序表里查找

操作思路

通过列表的首尾位置索引后相加,除以二,向下取整(“//”)。判断出二分法后的索引位置是否是查找的目标,若不是就根据目标大小与当前索引位置比较,判断使向前还是向后索引,如此循环。

SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。
  • 注意:循环退出的条件

1.递归法实现的代码:

1.2二分法 算法 第1张

 

 

2.非递归法实现的代码:

1.2二分法 算法 第2张

 

 

时间复杂度

  • 最优时间复杂度:O(1)
  • 最坏时间复杂度:O(logn)

 

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄