学习日记-02-关于 二分查找

对象:有序的元素列表(list)

目标:一个元素(target)

时间复杂度:O(logN) log以2为底

思路:设置一个循环,在每一次循环中都比较target和guess值的大小,其中guess值是整个有序数列的中值(mid index),若guess值小了就将元素列表缩小到后半段(mid+1,len(list)-1),若guess值大了就将列表缩小到前半段(0,mid-1),若guess等于target则返回index的值

循环结构有 for循环和while循环。

一般while 语句用于循环执行程序,即在某条件下,循环执行某段程序,以处理需要重复处理的相同任务。而for循环可以遍历任何序列的项目。在这个二分查找的小任务里,比较guess值和缩小范围在每一次循环中都是相同的,因此while循环更适合这里。

while循环的逻辑:当判断条件为true,执行语句,直到条件不满足,跳出。

二分查找直到范围缩小到只剩一个值的时候,停止。此时index_low = index_high

代码如下:


©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 当今社会,既非“黄金时代”,亦非“白银时代”,而是一个不折不扣的逐利时代。逐利时代依旧会有文青,只不过文青们会被嘲...
    海月先生阅读 1,209评论 3 9
  • Node.js 可以理解为能在操作系统上跑的js(不仅仅在浏览器) 还能当web服务器哟~ 用的Chrome V8...
    那就远走阅读 364评论 0 0
  • 在工作中,偶然心思一动,忽然觉得自己明白了理想主义与现实主义的区别:理想主义是大环境的事儿,而现实主义是小环境的事...
    哥舒阅读 202评论 0 0