問題描述##
折半查找
思路##
明顯的解法是從左到右掃描數(shù)據(jù)，其運行花費的是線性時間。然而，這個算法沒有用到該表已經(jīng)排序的事實，這就使得算法可能不是最好的。一個好的策略是驗證X是否是居中元素。如果是，則答案就找到了。如果X小于居中元素，那么我們可以應(yīng)用同樣的策略于居中元素左邊已經(jīng)排好序的子序列；同理，如果X大于居中元素，那么我們檢查數(shù)據(jù)的右半部分。
代碼##
public static <AnyType extends Comparable<? super AnyType>> int binarySearch(AnyType[] a, AnyType x) {
int low = 0, high = a.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid].compareTo(x) < 0) {
low = mid + 1;
} else if (a[mid].compareTo(x) > 0) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
分析##
根據(jù)上面的算法，二分查找的過程可以用二叉判定樹來描述。例如，有序表{44,45,47,50,65,70}的二叉判定樹如下圖所示：
二叉判定樹
在二分查找過程中，查找失敗時需要比較的關(guān)鍵字至多為
log2(N+1)向上取整（二叉樹的層數(shù)），查找成功時需要比較的關(guān)鍵字至多為log2(N+1)向上取整。二分查找的時間復(fù)雜度為O（log2N）。二分查找的平均性能和最壞性能相當(dāng)接近。其優(yōu)點是查找效率比順序查找高，缺點是要求查找有序表，并且二分查找只適用于順序存儲結(jié)構(gòu)，鏈?zhǔn)酱鎯Y(jié)構(gòu)的順序表無法采用二分查找算法。
二分查找提供了在O(logN)時間內(nèi)的contains操作，但是所有其他操作（特別是insert操作）均需要O(N)時間。在數(shù)據(jù)穩(wěn)定（即不允許插入操作和刪除操作）的應(yīng)用中，這種操作可能是非常有用的。此時輸入數(shù)據(jù)需要一次排序，但是此后的訪問會很快。有個例子是一個程序，它需要保留（產(chǎn)生于化學(xué)和物理領(lǐng)域的）元素周期表的信息。這個表是相對穩(wěn)定的，因為很少會引入新元素。元素名可以始終是排序的。由于大約只有110種元素，因此找出一個元素最多需要8次。但是執(zhí)行順序查詢就需要多得多的查找次數(shù)。
