演算法類型
divide and conquer, 搜尋演算法演算法目的
利用比對 key value 來對資料進行搜尋演算法描述
使用 binary search 的前提是資料必須是已經排序好的，接著再藉由比對資料堆中間位置的 key value 來將資料堆做二分法搜尋。舉例說明，假設有一排序好的數列如下圖:
現在假設我們要搜尋的數字是 3，就我們目前所得知的資訊，3 有可能出現在此數列的任何位置，所以目前的搜尋範圍是整個數列，我們先找出在搜尋範圍內中間位置的數字，如下圖:
.png)
我們在中間位置找到 4，很明顯的 4 不是我們要的 3，不過因為數列是已經排序好的而且 3 < 4，故我們可以確定 3 只有可能落在 4 的左邊而不可能會落在 4 的右邊，如下圖:
如此我們就可以拋棄右邊，接著繼續向左邊搜尋，所以現在的搜尋範圍變成只剩 4 的左邊，同之前的方法，直接去比對搜尋範圍中間位置的數字，如下圖:
.png)
我們在搜尋範圍中間找到 2，很明顯 2 不是我們要的 3，不過因為數列是已經排序好的而且 3 > 2，故我們可以確定 3 只有可能落在 2 的右邊而不可能會落在 2 的左邊，如下圖:
同之前的方法，我們繼續在搜尋範圍內找中間的數字做比對，以目前的情況來看，我們只剩下一個數字，如下圖:
.png)
恭喜，我們很幸運的找到 3 了，binary search 圓滿結束。如果一直二分到沒有範圍可以搜尋，則代表此數字不在數列裡。
最壞情況效率分析
設總資料量為 n, 分析單位為比較次數binary search 的最壞情況就是要搜尋的資料不在資料堆裡，依據最壞情況可以列出以下遞迴式:
T(n) = T(n / 2) + 1
T(1) = 1
根據 master theorem，可推出此演算法效率的最壞情況為 O(lgn)
程式實作
C
#include <stdio.h>
int binarySearch(int *, int, int);
int main() {
int arr[8] = {1, 2, 3, 4, 5, 6, 7, 8};
int arrLength = 8;
int findNum = 3;
int findIndex = binarySearch(arr, arrLength, findNum);
if (findIndex == -1)
printf("The number %d is not in the sequence\n", findNum);
else
printf("The number %d is at index %d\n", findNum, findIndex);
return 0;
}
int binarySearch(int *arr, int arrLength, int findNum) {
int low = 0;
int high = arrLength - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (findNum > arr[mid])
low = mid + 1;
else if (findNum == arr[mid])
return mid;
else
high = mid - 1;
}
return -1;
}
Java
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int findNum = 3;
int findIndex = binarySearch(arr, findNum);
if (findIndex == -1)
System.out.printf("The number %d is not in the sequence\n", findNum);
else
System.out.printf("The number %d is at index %d\n", findNum, findIndex);
}
private static int binarySearch(int[] arr, int findNum) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (findNum > arr[mid])
low = mid + 1;
else if (findNum == arr[mid])
return mid;
else
high = mid - 1;
}
return -1;
}
}
Python
def binarySearch(arr, findNum):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) / 2
if findNum > arr[mid]:
low = mid + 1
elif findNum == arr[mid]:
return mid
else:
high = mid - 1
return -1
arr = [1, 2, 3, 4, 5, 6, 7, 8]
findNum = 3
findIndex = binarySearch(arr, findNum)
if findIndex == -1:
print "The number %d is not in the sequence" % (findNum)
else:
print "The number %d is at index %d" % (findNum, findIndex)
