二分查找的簡單理解

• 2022 年 7 月 4 日
• 筆記
• 數據結構與算法, 查找, 算法

詳細描述

二分查找的搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索算法每一次比較都使搜索範圍縮小一半。

二分查找詳細的執行步驟如下：

1. 在有序表中，取中間記錄作為比較對象；
2. 若給定值與中間記錄的關鍵字相等，則查找成功；
3. 若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續查找；
4. 若給定值大於中間記錄的關鍵字，則在中間記錄的右半區繼續查找；
5. 不斷重複步驟 1~4，直到查找成功，或所有查找區域無記錄，查找失敗為止。

算法圖解

問題解疑

二分查找算法有哪些局限性？

二分查找算法需要按照下標隨機訪問。所以更適合數組結構，而不適合鏈表結構，數組按照下標隨機訪問數據的時間複雜度是 \(O(1)\)，而鏈表隨機訪問的時間複雜度是 \(O(n)\)。

二分查找針對的是有序數。二分查找只能用在插入、刪除操作不頻繁，一次排序多次查找的場景中，針對動態變化的數據集合，二分查找將不再適用。

數據量太小不適合二分查找。在一個大小為 10 的數組中查找一個元素，不管用二分查找還是順序遍歷，查找速度都差不多，只有數據量比較大的時候，二分查找的優勢才會比較明顯。

數據量太大也不適合二分查找。二分查找是作用在數組這種數據結構之上的，太大的數據用數組存儲比較吃力，也就不能用二分查找了。

二分查找算法有哪些變形？

• 查找第一個值等於給定值的元素
• 查找最後一個值等於給定值的元素
• 查找第一個大於等於給定值的元素
• 查找最後一個小於等於給定值的元素

代碼實現

查找接口

package cn.fatedeity.algorithm.search;

public interface Search {
    int search(int[] numbers, int target);
}

二分查找類

package cn.fatedeity.algorithm.search;

/**
 * 二分查找類
 */
public class BinarySearch implements Search {
    private int search(int[] numbers, int target, int left, int right) {
        if (left > right) {
            return -1;
        } else if (left == right) {
            if (numbers[left] == target) {
                return left;
            } else {
                return -1;
            }
        }
        if (target < numbers[left] || target > numbers[right]) {
            return -1;
        }

        int mid = (left + right) >> 1;
        if (numbers[mid] > target) {
            return this.search(numbers, target, left, mid - 1);
        } else if (numbers[mid] < target) {
            return this.search(numbers, target, mid + 1, right);
        } else {
            return mid;
        }
    }

    @Override
    public int search(int[] numbers, int target) {
        return this.search(numbers, target, 0, numbers.length - 1);
    }
}