Java面試題Java寫一個折半查找
來源：文萃谷 1.86W
引導語：折半查找是指如果不是從一組隨機的序列裏查找,而是從一組排好序的序列裏找出某個元素的位置,則可以有更快的算法。以下是本站小編分享給大家的用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(>>>是邏輯右移，是不帶符號位的右移)
