2019独角兽企业重金招聘Python工程师标准>>>
二分查找时间复杂度的计算 博客分类： 算法 ?二分查找的基本思想是将n个元素分成大致相等的两部分，去a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度无非就是while循环的次数！
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,....n/2^k，其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O()=O(logn)
?
?
二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。二分查找的一个条件是待查询的数组是有序的，我们假设这里的数组是升序的。二分查找的主要思路就是设定两个指针start和end分别指向数组元素的收尾两端，然后比较数组中间结点arry[mid]和待查找元素。如果待查找元素小于中间元素，那么表明带查找元素在数组的前半段，那么将end=mid-1，如果待查找元素大于中间元素，那么表明该元素在数组的后半段，将start=mid+1;如果中间元素等于待查找元素，那么返回mid的值。二分查找可以使用递归和非递归的方法来解决
?
?
?
?
转载于:https://my.oschina.net/xiaominmin/blog/1597308
93850772