Java 使用Binary Search 二元搜索法尋找陣列中的值

如果要從一個有排序的陣列中尋找一個特定的數，可以利用binary search來加快尋找的速度。

Binary search的時間複雜度為O(log(n))，也就是要從n個元素中搜尋到某一個元素，則最多要搜尋log(n)次。

下面範例為利用binary search從一個整數陣列中尋找特定指定的數。

/**
 * @param sortedArray
 *            排序好的陣列
 * @param target
 *            尋找的目標值
 * @param start
 *            尋找的開始index，若超出陣列範圍則返回 -1
 * @param end
 *            尋找的結束index，若超出陣列範圍則返回 -1
 * @return 如果找到目標值，返回目標值在陣列的index值，否則返回 -1
 */
private static int binarySerchForSortedArray(int[] sortedArray, int  target, int start, int end) {
    if (start < 0 || end >= sortedArray.length) {
        return -1;
    }
    while (start <= end) {
        int mid = (start + end) / 2;
        if (sortedArray[mid] == target) {
            return mid;
        } else if (target > sortedArray[mid]) {
            start = mid + 1;
        } else if (target < sortedArray[mid]) {
            end = mid - 1;
        }
    }
    return -1;
}

如果值接從陣列中的第一個元素找到最後一個元素，這種搜尋方法稱做線性搜索(linear search)，其搜尋的時間複雜度為O(n)，也就是從n個元素中搜尋到某一個元素，則最多要搜尋n次。

假設今天要從一個有排序且含100個值的陣列中找到某一特定值，則binary saerch的時間複雜度為log₂(100) = 6.64（次），而linear search的時間複雜度為100（次），由此可見binary search的速度會比linear search快上許多。

在Java的java.util.Arrays.binarySearch()已經提供了同樣的方法可直接使用。

參考：

• 大毛電腦科學筆記 - #9 Binary search 的 Big O ?
• Binary Search Algorithm in Java
• 為什麼Binary Search 二元搜索法的時間複雜度是O(log(n))