戳藍字“CSDN云計算”關注我們哦！

作者 | 蠢萌的小灰

來源 | 程序員小灰

—————? 第二天? —————

什么意思呢？我們來舉兩個栗子：

給定一個有序數組?

2，5，7，9，12，14，20，26，30

Case 1：

Case 2：

————————————

為什么說這樣效率最高呢？因為每一次選擇數字，無論偏大還是偏小，都可以讓剩下的選擇范圍縮小一半。

給定范圍0到1000的整數：

第一次我們選擇500，發現偏大了，那么下一次的選擇范圍，就變成了1到499：

第二次我們選擇250，發現還是偏大了，那么下一次的選擇范圍，就變成了1到249：

第三次我們選擇125，發現偏小了，那么下一次的選擇范圍，就變成了126到249：

以此類推，最壞的情況需要猜測多少次呢？答案是 log1000 = 10次，也就是讓原本的區間范圍進行10次 “折半”。

剛才我們所分析的是猜數字的游戲。如果我們把場景轉換成最初的面試問題：在包含1000個整型元素的有序數組中查找某個特定整數，又該如何去做呢？

同樣道理，我們可以首先判斷下標是499的元素（因為數組下標從0開始，到999結束），如果元素大于要查找的整數，我們再去判斷下標是249的元素，然后判斷下標124的元素......以此類推，直到最終找到想要的元素，或者選擇范圍等于0為止。

上述這個過程，就是所謂的二分查找算法，查找的時間復雜度是log（n）。

public static int binarySearch(int []array,int target){ static int binarySearch(int []array,int target){

//查找范圍起點//查找范圍起點

int start=0;int start=0;

//查找范圍終點//查找范圍終點

int end=array.length-1;int end=array.length-1;

//查找范圍中位數//查找范圍中位數

int mid;int mid;

//迭代進行二分查找

while(start<=end){while(start<=end){

mid=(start+end)/2;end)/2;

if(array[mid]==target){if(array[mid]==target){

return mid;return mid;

}else if(array[mid]<target){else if(array[mid]<target){

start=mid+1;1;

}else{else{

end=mid-1;end=mid-1;

}

}

return -1;return -1;

}

public static void main(String[] args) { static void main(String[] args) {

int[] array = new int[1000];int[] array = new int[1000];

for(int i=0; i<1000;i++){for(int i=0; i<1000;i++){

array[i] = i;

}

System.out.println(binarySearch(array, 173));System.out.println(binarySearch(array, 173));

}

福利

掃描添加小編微信，備注“姓名+公司職位”，加入【云計算學習交流群】，和志同道合的朋友們共同打卡學習！

推薦閱讀：

• IEEE 回應禁止華為系審稿人;WiFi聯盟、藍牙聯盟已恢復華為成員資格；中國計算機學會：暫時中止與IEEE通信學會合作……

• ARM 發布新一代 CPU 和 GPU，實現 20% 性能提升！

• 前端開發 20 年變遷史
  

• 北漂杭漂的程序員，是如何買到第一套房子？
  

• “愛裝X”開源組織：“教科書級”AI知識樹究竟長什么樣？

• 500行Python代碼打造刷臉考勤系統

• 權游播完了, 你在罵爛尾, 有人卻悄悄解鎖了新操作……
  

真香，朕在看了！

總結

以上是生活随笔為你收集整理的漫画：什么是二分查找？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。