- 相關(guān)推薦
Java面試題Java寫一個折半查找
引導(dǎo)語：折半查找是指如果不是從一組隨機的序列里查找,而是從一組排好序的序列里找出某個元素的位置,則可以有更快的算法。以下是百分網(wǎng)小編分享給大家的用Java面試題Java寫一個折半查找，歡迎閱讀參考!
用Java寫一個折半查找
答：折半查找，也稱二分查找、二分搜索，是一種在有序數(shù)組中查找某一特定元素的搜索算法。搜素過程從數(shù)組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結(jié)束;如果某一特定元素大于或者小于中間元素，則在數(shù)組大于或小于中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數(shù)組已經(jīng)為空，則表示找不到指定的元素。這種搜索算法每一次比較都使搜索范圍縮小一半，其時間復(fù)雜度是O(logN)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
import java.util.Comparator;public class MyUtil { public static <T extends Comparable<T>> int binarySearch(T[] x, T key) { return binarySearch(x, 0, x.length- 1, key); } // 使用循環(huán)實現(xiàn)的二分查找 public static <T> int binarySearch(T[] x, T key, Comparator<T> comp) { int low = 0; int high = x.length - 1; while (low <= high) { int mid = (low + high) >>> 1; int cmp = comp.compare(x[mid], key); if (cmp < 0) { low= mid + 1; } else if (cmp > 0) { high= mid - 1; } else { return mid; } } return -1; } // 使用遞歸實現(xiàn)的二分查找 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(key.compareTo(x[mid])== 0) { return mid; } else if(key.compareTo(x[mid])< 0) { return binarySearch(x,low, mid - 1, key); } else { return binarySearch(x,mid + 1, high, key); } } return -1; }} |
說明：上面的代碼中給出了折半查找的兩個版本，一個用遞歸實現(xiàn)，一個用循環(huán)實現(xiàn)。需要注意的是計算中間位置時不應(yīng)該使用(high+ low) / 2的方式，因為加法運算可能導(dǎo)致整數(shù)越界，這里應(yīng)該使用以下三種方式之一：low + (high – low) / 2或low + (high – low) >> 1或(low + high) >>> 1(>>>是邏輯右移，是不帶符號位的右移)
【Java面試題Java寫一個折半查找】相關(guān)文章：
Java面試題（精選）06-30
java面試題05-20
Java線程面試題08-25
高級Java面試題精選11-02
Java 問答面試題09-03
Java原理面試題07-13
經(jīng)典Java面試題之Java中Char類型的運算07-30
C語言二分查找（折半查找）算法及代碼08-07