二分查找时间复杂度推导

由于二分查找每次查询都是从数组中间切开查询，所以每次查询，剩余的查询数为上一次的一半，从下表可以清晰的看出查询次数与剩余元素数量对应关系

表-查询次数及剩余数

第几次查询        剩余待查询元素数量

1                            N/2

2                            N/(2^2)

3                            N/(2^3)

……

K                            N/(2^K)

从上表可以看出N/(2^K)肯定是大于等于1，也就是N/(2^K)>=1，我们计算时间复杂度是按照最坏的情况进行计算，也就是是查到剩余最后一个数才查到我们想要的数据，也就是

N/(2^K)=1

=>N=2^K

=>K=log2N

所以二分查找的时间复杂度为O(log2N)

代码

/** * 二分查找 *@paramarr 指定查询的数组 *@paramsearchNum 要查询的数字 *@return返回查询的的结果（数组中的索引），没有则返回-1 */

   publicstaticintbinerySearch(int[] arr,intsearchNum){

       // 初始化左侧索引

       intleftIndex =0;

       // 初始化右侧索引

       intrightIndex = arr.length -1;

       while(leftIndex <= rightIndex) {

           // 计算中间索引

           intmid = (leftIndex + rightIndex) >>>1;//主要防止溢出，就是除以2的意思

           // 如果查询的数等于中间索引对应的数组里的数，则返回mid索引，并退出循环

           if(searchNum == arr[mid]) {

               returnmid;

            }

           // 判断并计算右侧索引

           if(searchNum < arr[mid]) {

                rightIndex = mid -1;

            }

           // 判断并计算左侧索引

           if(searchNum > arr[mid]) {

                leftIndex = mid +1;

            }

        }

       return-1;

    }

    本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。