二分查找算法的簡單介紹

今天我們來學(xué)習(xí)一下二分查找算法，也叫做折半查找算法。使用二分查找算法的前提是數(shù)據(jù)需要是有序的。二分查找的思想非常簡單，很容易理解，就是每次取中間位置的數(shù)和要找的數(shù)作比較，通過判斷是大還是小來重新選擇中間位置，直到找到。但是在實際的應(yīng)用中卻并不簡單，因為我們實際碰到的問題不會像一個排好序的數(shù)組，然后讓我們找出其中是不是包含某一個數(shù)這么簡單。

簡單的例子

我們在生活中也會經(jīng)常遇到二分查找的使用，比如我們應(yīng)該都玩過猜數(shù)字的游戲，我隨便寫一個 1 到 100 中間的數(shù)，然后你來猜我寫的是多少，每次你猜之后我會告訴你是大了還是小了，直到你猜中為止。所有人都知道，我們每次都取中間數(shù)去猜，然后根據(jù)提示大了小了重新選擇中間數(shù)，直到猜中。這樣是速度最快的辦法。這里我們用到的就是二分查找算法。

比如我寫的數(shù)是 36，使用二分法的步驟就像下圖展示的。

7 次就猜出來我寫的數(shù)，還是很快的是吧。那如果最開始的范圍是 1-1000 或者 1-10000 甚至更大的范圍需要多少次呢？感興趣的可以自己試試。

時間復(fù)雜度

我們通過上邊簡單的例子也了解了二分查找算法的原理和思想，下面我們來分析一下二分查找算法的時間復(fù)雜的。

我們假設(shè)數(shù)據(jù)的大小為 n，每次查找后數(shù)據(jù)都會變?yōu)樵瓉淼囊话耄簿褪?n/2，然后直到找到最后要找的值，最壞的情況就是數(shù)據(jù)中沒有我們要找的值，直到查找區(qū)間被縮小為空，才停止。

查找區(qū)間的大小變化：

最壞的情況就是 n/2^k = 1 的時候，k 就是總共縮小的次數(shù)，每次縮小我們只需要比較兩個數(shù)的大小，所以，一共有 k 次比較，時間復(fù)雜度為 O(k)。
通過 n/2^k = 1，我們可以求得 k = log2(n)，所以最后的時間復(fù)雜度為O(logn)。

我們在深入的了解一下 O(logn) 這種時間復(fù)雜度。我們首先來看一下 logn 的函數(shù)的數(shù)學(xué)圖像。

image.png

image.png

圖1中橫坐標的值是從 -1024 到 1024 ，而 y 的值最大也不過才是 10。
圖2中橫坐標的值時從 -4294967296 到 4294967296，也就是 -2^32 到 2^32 ，y 的最大值是 32 ，可見 x 都大到了四十多億了，y 的值不過才32?？梢姸植檎以跀?shù)據(jù)量是如此巨大的時候查找的次數(shù)也不過才幾十次。所以說二分查找算法是非常高效的。

代碼實現(xiàn)

我們已經(jīng)了解了二分法的思想和查找過程。下面通過具體的代碼來實現(xiàn)二分查找算法。
最簡單的情況是已經(jīng)排好序的沒有重復(fù)元素的數(shù)組，然后我們找出數(shù)組中有沒有與給定值相等的元素。

public int BinarySearch(int[] array,int n, int value){
    int low = 0;
    int high = n - 1;
    while(low<=high){
        int mid = (low + high) / 2;
        if(array[mid] > value){
            high = mid - 1;
        }
        else if(array[mid] > value){
            low = mid + 1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

當(dāng)然，我們上邊只是最簡單一種情況，下面我們稍微增加一點難度。如果數(shù)組中有重復(fù)的元素的話。我們算法該怎么寫呢？

• 查找第一個值等于給定值的元素

public int BinarySearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == 0) || (a[mid - 1] != value)) return mid;
          else high = mid - 1;
        }
    }
    return -1;
}

我們判斷 array[mid] 與給定值大小關(guān)系有大于小于和等于，當(dāng)大于或小于的時候和最簡單沒有重復(fù)元素時候一樣，只需要更新 high 和 low 的值就協(xié)議了。但當(dāng)?shù)扔诘臅r候，我們不能立馬返回，因為我們不知道這個是不是第一個等于給定值的元素。所以我們要判斷，如果 mid 等于 0 的話，是數(shù)組的第一個元素，那么肯定是第一個等于給定值的；如果 mid 不等于 0 ，我們查看前一個元素 array[mid-1] 的值如果不等于 value，那么 array[mid] 就是第一個等于 value 的值，如果前一個元素等于 value 的話，我們需要更新 high 的值，因為要找的元素肯定在 [low, mid-1]之間。

• 查找最后一個值等于給定值的元素
  上邊我們求得是第一個等于給定值的元素，這次我們來找最后一個。只需要將上邊的代碼稍微改動一下就可以了

public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else if (a[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
            else low = mid + 1;
        }
    }
    return -1;
}

參照上邊查找第一個等于給定值的講解，這個也就很容易理解了。

• 查找第一個大于等于給定值的元素
  在數(shù)組中，查找第一個大于等于給定值的元素，比如數(shù)組 [1,4,4,5,7,9]，查找第一個大于等于 6 的元素，那就是 7。

public int bsearch(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] >= value) {
            if ((mid == 0) || (a[mid - 1] < value)) return mid;
            else high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

這個和第一個等于給定值的情況多了大于的條件，所以我們只需要把原來的等于的情況和大于的情況和到一起來判斷就可以了

• 查找最后一個小于等于給定值的元素

public int bsearch7(int[] a, int n, int value) {
    int low = 0;
    int high = n - 1;
    while (low <= high) {
        int mid =  low + ((high - low) >> 1);
        if (a[mid] > value) {
            high = mid - 1;
        } else {
            if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
            else low = mid + 1;
        }
    }
    return -1;
}

有了上邊的做鋪墊，這個應(yīng)該很容易就理解了。這里就不做過多解釋了。

總結(jié)一下

通過上邊我們的代碼的實例，總結(jié)出我們寫二分查找算法時候需要注意的幾個地方。
1、終止條件的正確性
2、區(qū)間上下界的更新
3、返回值的選擇
注意到這幾個條件后，我們寫的算法應(yīng)該就不容易有 bug 了。
雖然二分查找非常的簡單高效，但也有它的局限性。

• 數(shù)據(jù)結(jié)構(gòu)必須有序
  二分查找要求數(shù)據(jù)是有序的，這樣我們才能使用二分查找。
• 依賴的是順序表結(jié)構(gòu)
  也就是數(shù)組，因為二分查找是通過下標來訪問元素的，如果是鏈表的話，二分查找的時間復(fù)雜度就非常高了。
• 數(shù)據(jù)太小不適合
  如果數(shù)據(jù)量很小，完全沒必要使用二分法了，順序遍歷比較就可以了。
• 數(shù)據(jù)太大不適合
  你上邊不是說了二分法很適合用在大數(shù)據(jù)量的查找嗎，而且越大的數(shù)據(jù)量越能體現(xiàn)二分查找算法的高效嗎。為什么又不適合了呢。因為二分查找依賴于想數(shù)組這樣的順序表結(jié)構(gòu)，而這種結(jié)構(gòu)為了提供隨機訪問，要就內(nèi)存空間是連續(xù)的。
  也就是如果我們要處理 10G 的數(shù)據(jù)，我們需要 10G 的連續(xù)的內(nèi)存空間，如果你內(nèi)存還有很多，可都是不連續(xù)的，分散的，同樣不能使用二分查找。