引導語:折半查詢是指如果不是從一組隨機的序列裡查詢,而是從一組排好序的序列裡找出某個元素的位置,則可以有更快的演算法。以下是本站小編分享給大家的用Java面試題Java寫一個折半查詢,歡迎閱讀參考!
用Java寫一個折半查詢
答:折半查詢,也稱二分查詢、二分搜尋,是一種在有序陣列中查詢某一特定元素的搜尋演算法。搜素過程從陣列的中間元素開始,如果中間元素正好是要查詢的元素,則搜素過程結束;如果某一特定元素大於或者小於中間元素,則在陣列大於或小於中間元素的.那一半中查詢,而且跟開始一樣從中間元素開始比較。如果在某一步驟陣列已經為空,則表示找不到指定的元素。這種搜尋演算法每一次比較都使搜尋範圍縮小一半,其時間複雜度是O(logN)。
123456789101112131415161718192021222324252627282930313233343536373839404142434445 | import arator; public class MyUtil {
public static <T extends Comparable<T>> int binarySearch(T[] x, T key) {
return binarySearch(x, 0 , th- 1 , key);
}
// 使用迴圈實現的二分查詢
public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) {
int low = 0 ;
int high = th - 1 ;
while (low <= high) {
int mid = (low + high) >>> 1 ;
int cmp = are(x[mid], key);
if (cmp < 0 ) {
low= mid + 1 ;
}
else if (cmp > 0 ) {
high= mid - 1 ;
}
else {
return mid;
}
}
return - 1 ;
}
// 使用遞迴實現的二分查詢
private static <T extends Comparable<T>> int binarySearch(T[] x, int low, int high, T key) {
if (low <= high) {
int mid = low + ((high -low) >> 1 );
if (areTo(x[mid])== 0 ) {
return mid;
}
else if (areTo(x[mid])< 0 ) {
return binarySearch(x,low, mid - 1 , key);
}
else {
return binarySearch(x,mid + 1 , high, key);
}
}
return - 1 ;
} } |
說明:上面的程式碼中給出了折半查詢的兩個版本,一個用遞迴實現,一個用迴圈實現。需要注意的是計算中間位置時不應該使用(high+ low) / 2的方式,因為加法運算可能導致整數越界,這裡應該使用以下三種方式之一:low + (high – low) / 2或low + (high – low) >> 1或(low + high) >>> 1(>>>是邏輯右移,是不帶符號位的右移)