漫畫：什麼是二分查找？

作者 | 萌蠢的小灰

責編 | 胡巍巍

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

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

給定一個有序數組

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){
//查找範圍起點
int start=0;
//查找範圍終點
int end=array.length-1;
//查找範圍中位數
int mid;
while(start<=end){
//mid=(start+end)/2 有可能溢出
mid=start+(end-start)/2;
if(array[mid]==target){
return mid;
}else if(array[mid]<target){
start=mid+1;
}else{
end=mid-1;
}
}
return -1;
}
public static void main(String[] args) {
int[] array = new int[1000];
for(int i=0; i<1000;i++){
array[i] = i;
}
System.out.println(binarySearch(array, 173));
}

本文僅代表作者的觀點，不代表 CSDN 立場。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！