網頁

2018/8/28

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的時間複雜度為log2(100) = 6.64(次),而linear search的時間複雜度為100(次),由此可見binary search的速度會比linear search快上許多。

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


參考:

1 則留言:

  1. Nice explanation with example. Thanks for sharing.

    Cheers,
    https://www.flowerbrackets.com/binary-search-java/

    回覆刪除