如果要從一個有排序的陣列中尋找一個特定的數,可以利用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 則留言:
Nice explanation with example. Thanks for sharing.
Cheers,
https://www.flowerbrackets.com/binary-search-java/
張貼留言