經典演算法 binary search 二分查找怎麼實現？

feellikelearning March 15, 2020 0 Comments

二分查找很經典，當年看哈佛CS50是這麼講解的：怎麼在字典里找某個單詞？我們知道字典是按字母順序排好序的。比如目標單詞是cat，翻開字典中間，現在是g開頭的詞，那麼我們知道cat肯定不在後半部分，那麼可以把字典撕開，扔了後半部分。然後重複以上過程，中間翻開，這回是b開頭的，就可以把前半部分仍了。如此下去，每次都把要搜索的空間減少一半，這樣只用O(lgN)時間就能找到目標。不然的話一頁頁找的話就需要O(N)。雖然演算法不複雜，但是要寫對還是不容易的，以下經典實現最好背下來，內化到自己的知識庫，就不用擔心用到的時候邊界條件不對。不然很容易進入死循環不返回，親身經歷。

代碼如下：

Java

import java.util.Arrays;
import java.util.List;

public class Binarysearch {
    public static boolean binarySearch(int target, List<Integer> sortedlist) {
        if (sortedlist == null || sortedlist.isEmpty()) {
            return false;
        }
        int lower = 0;
        int upper = sortedlist.size()-1;
        while (lower <= upper) {
            int m = lower + (upper - lower) / 2;
            if (target == sortedlist.get(m)) {
                return true;
            } else if (target < sortedlist.get(m)) {
                upper = m - 1;
            } else {
                lower = m + 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        List<Integer> sortedList = Arrays.asList(1, 3, 3, 7, 20, 48, 64, 72, 1024);
        int [] targets = {20, 32, 55, 72, 100};
        for (int target : targets) {
            System.out.println(String.format("%d in list? %b", target, binarySearch(target, sortedList)));
        }
    }
}

主要以下要點

• while裡面條件要是 lower <= upper
• update lower bound 要是 m + 1
• update upper bound 要是 m - 1
• 計算中指用 m = lower + (upper - lower) / 2，而不是 (upper + lower) / 2，這樣可以去除整數相加overflow問題。當然如果類型是bigint之類就無所謂了。