由于二分查找每次查詢都是從數(shù)組中間切開查詢，所以每次查詢副硅，剩余的查詢數(shù)為上一次的一半克锣，從下表可以清晰的看出查詢次數(shù)與剩余元素?cái)?shù)量對(duì)應(yīng)關(guān)系
表-查詢次數(shù)及剩余數(shù)
第幾次查詢????????剩余待查詢?cè)財(cái)?shù)量
1????????????????????????????N/2
2????????????????????????????N/(2^2)
3????????????????????????????N/(2^3)
……
K? ? ? ? ? ? ????????????????N/(2^K)
從上表可以看出N/(2^K)肯定是大于等于1感帅，也就是N/(2^K)>=1强饮，我們計(jì)算時(shí)間復(fù)雜度是按照最壞的情況進(jìn)行計(jì)算，也就是是查到剩余最后一個(gè)數(shù)才查到我們想要的數(shù)據(jù)忍级，也就是
N/(2^K)=1
=>N=2^K
=>K=log2N
所以二分查找的時(shí)間復(fù)雜度為O(log2N)
代碼
/** * 二分查找 *@paramarr 指定查詢的數(shù)組 *@paramsearchNum 要查詢的數(shù)字 *@return返回查詢的的結(jié)果（數(shù)組中的索引）帆谍，沒有則返回-1 */
???publicstaticintbinerySearch(int[] arr,intsearchNum){
???????// 初始化左側(cè)索引
???????intleftIndex =0;
???????// 初始化右側(cè)索引
???????intrightIndex = arr.length -1;
???????while(leftIndex <= rightIndex) {
???????????// 計(jì)算中間索引
???????????intmid = (leftIndex + rightIndex) >>>1;//主要防止溢出，就是除以2的意思
???????????// 如果查詢的數(shù)等于中間索引對(duì)應(yīng)的數(shù)組里的數(shù)轴咱，則返回mid索引汛蝙，并退出循環(huán)
???????????if(searchNum == arr[mid]) {
???????????????returnmid;
??????????? }
???????????// 判斷并計(jì)算右側(cè)索引
???????????if(searchNum < arr[mid]) {
??????????????? rightIndex = mid -1;
??????????? }
???????????// 判斷并計(jì)算左側(cè)索引
???????????if(searchNum > arr[mid]) {
??????????????? leftIndex = mid +1;
??????????? }
??????? }
???????return-1;
??? }
????本文轉(zhuǎn)自網(wǎng)絡(luò)文章烈涮，轉(zhuǎn)載此文章僅為分享知識(shí)，如有侵權(quán)窖剑，請(qǐng)聯(lián)系博主進(jìn)行刪除坚洽。
