數(shù)據(jù)結(jié)構(gòu)與算法--查找之順序查找和二分查找
符號(hào)表的目的是將一個(gè)鍵和一個(gè)值關(guān)聯(lián)起來介汹，可以將一對鍵值對插入到符號(hào)表中仰担，也可以根據(jù)給定的鍵從符號(hào)表所有的鍵值對中快速或者直接找到相對應(yīng)的值咱娶。對于鍵和值躯肌，我們作如下約定，以后的實(shí)現(xiàn)都遵循這些約定炉擅。
- 每個(gè)鍵只對應(yīng)一個(gè)值辉懒，也就是說不允許存在重復(fù)的鍵
- 新插入的鍵值對在表中鍵已經(jīng)存在，此時(shí)稱為沖突谍失，讓新的值取代舊的值
- 鍵不能為空null眶俩，因?yàn)樵诒容^中會(huì)調(diào)用鍵的equals或者compareTo方法；若為空會(huì)造成空指針異常
- 值不能為空null快鱼，因?yàn)樵谖覀兊膶?shí)現(xiàn)中颠印，當(dāng)查找一個(gè)不存在的鍵時(shí)，默認(rèn)返回null抹竹。因此我們可以用
get(Key key)判斷某個(gè)鍵在表中是否存在线罕；也可以用put(Key key, null)將某鍵值對刪除（延時(shí)實(shí)現(xiàn)）。
無序鏈表的順序查找
順序查找也就是遍歷表中元素窃判，鏈表實(shí)現(xiàn)即每個(gè)結(jié)點(diǎn)都表示一個(gè)鍵值對钞楼。如get(Key key)方法，查找表中所有鍵值對袄琳，如果匹配成功就返回相應(yīng)的值询件，否則返回null；put(Key key, Value value)方法也是查找表中所有鍵值對唆樊，如果鍵已經(jīng)存在就更新值宛琅，否則在鏈表頭插入這個(gè)新的鍵值對。實(shí)現(xiàn)起來很簡單窗轩，我們來看代碼。
package Chap8;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.Set;
public class SequentialST<Key, Value> {
private Node first;
private int N;
private class Node {
Key key;
Value value;
Node next;
public Node(Key key, Value value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public Value get(Key key) {
for (Node cur = first; cur != null; cur = cur.next) {
if (key.equals(cur.key)) {
return cur.value;
}
}
return null;
}
// 若是鍵不存在座咆，則返回一個(gè)指定的默認(rèn)值
public Value getDefault(Key key, Value value) {
for (Node cur = first; cur != null; cur = cur.next) {
if (key.equals(cur.key)) {
return cur.value;
}
}
return value;
}
public void put(Key key, Value value) {
// 如果傳入null痢艺，就是刪除鍵值對
if (value == null) {
delete(key);
return;
}
for (Node cur = first; cur != null; cur = cur.next) {
if (key.equals(cur.key)) {
cur.value = value;
return;
}
}
/* 新鍵值對。new Node的next指向first介陶，然后取代它成為新的first, 是以下代碼的簡化版
Node oldfirst = first;
first = new Node();
first.next = oldfirst;
*/
first = new Node(key, value, first);
N++;
}
// 未采用的延時(shí)刪除堤舒，使用下面的delete
// public void delete(Key key) {
// put(key, null);
// }
public Value delete(Key key) {
if (isEmpty()) {
return null;
}
Node cur = first;
Value value = null;
// 刪除的鍵值對如果在鏈表頭，處理方式不一樣
if (key.equals(cur.key)) {
value = cur.value;
Node next = cur.next;
// 下面三行是幫助垃圾回收
cur.key = null;
cur.value = null;
cur.next = null;
first = next;
N--;
} else {
// 現(xiàn)在pre是first哺呜，而cur是first的下一個(gè)結(jié)點(diǎn)
Node pre = cur;
cur = cur.next;
while (cur != null) {
if (key.equals(cur.key)) {
value = cur.value;
Node next = cur.next;
// 下面三行是幫助垃圾回收
cur.key = null;
cur.value = null;
cur.next = null;
pre.next = next;
N--;
return value;
}
// 下輪比較指向下一個(gè)結(jié)點(diǎn)舌缤，所以更新pre和cur
pre = cur;
cur = cur.next;
}
}
return value;
}
public Set<Key> keys() {
// 保證和values是一樣的順序
Set<Key> keys = new LinkedHashSet<>();
for (Node cur = first;cur != null;cur = cur.next) {
keys.add(cur.key);
}
return keys;
}
public Collection<Value> values() {
Collection<Value> values = new ArrayList<>();
for (Node cur = first;cur != null;cur = cur.next) {
values.add(cur.value);
}
return values;
}
@Override
public String toString() {
if (isEmpty()) {
return "{}";
}
StringBuilder sb = new StringBuilder();
sb.append("{");
Node cur = first;
while (true) {
sb.append(cur.key).append("=").append(get(cur.key));
if (cur.next == null) {
return sb.append("}").toString();
} else {
sb.append(", ");
}
cur = cur.next;
}
}
public boolean contains(Key key) {
return get(key) != null;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
public static void main(String[] args) {
SequentialST<String, Integer> st = new SequentialST<>();
st.put("admin", 8888);
st.put("password", 123456);
st.put("pcNumber", 5);
st.put("money", 6666);
Integer password = st.delete("password");
st.delete("money");
System.out.println(password);
System.out.println(st.get("pcNumber"));
System.out.println(st.get("admin"));
System.out.println(st.keys());
System.out.println(st.values());
System.out.println(st);
}
}
get方法沒什么好說的，有一個(gè)getDefault方法，當(dāng)給出的鍵不存在時(shí)国撵，將返回一個(gè)由調(diào)用者自定義的默認(rèn)值陵吸。put方法中，如果值傳入null介牙，相當(dāng)于是刪除該鍵值對壮虫，所以調(diào)用了delete。否則遍歷鏈表环础，如果查找到鍵已經(jīng)存在囚似，則用新的value取代舊的value；如果沒找到线得，說明這是新的鍵值對饶唤，直接插入到鏈表頭（相當(dāng)于push操作）。
重點(diǎn)看delete方法贯钩，我們并不打算用延時(shí)實(shí)現(xiàn)——雖然它相當(dāng)簡單募狂。如下
public void delete(Key key) {
put(key, null);
}
注意：如果使用上述實(shí)現(xiàn)，put方法頭幾行判斷就得去掉魏保，否則兩個(gè)方法會(huì)互相調(diào)用導(dǎo)致StackOverflow熬尺。我們的實(shí)現(xiàn)是即時(shí)刪除的，其實(shí)就是鏈表刪除結(jié)點(diǎn)的操作谓罗。即時(shí)delete中粱哼，需要一個(gè)Node pre指針，用于指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)檩咱，如果你對鏈表結(jié)點(diǎn)的刪除操作熟悉的話，應(yīng)該清楚為什么需要這個(gè)pre指針。鏈表頭的刪除和其他地方結(jié)點(diǎn)的刪除操作還有些不一樣：刪除鏈表頭只需first.next成為新的first霸褒；其他位置的刪除抖誉，刪除的是結(jié)點(diǎn)cur耿币，需要將cur的前一個(gè)結(jié)點(diǎn)pre的next指向cur的next塑悼，即pre.next = cur.next。
keys和values方法可以返回符號(hào)表中所有的鍵值對巷屿，鍵是唯一的所以用了Set存放旬昭。
在含有N對鍵值對的無序鏈表中绪杏，未命中和插入新鍵值對的比較次數(shù)均為N腔彰，命中的最壞情況為比較N次（最后一個(gè)結(jié)點(diǎn)才匹配成功）辖佣。
有序數(shù)組中的二分查找
上面鏈表實(shí)現(xiàn)的符號(hào)表中霹抛，表是無序的。如果能在插入過程中保證表一直有序卷谈，在查找的時(shí)候就不必順序查找杯拐，使用二分查找可大大提高查找的效率。我們需要兩個(gè)數(shù)組世蔗，Key[]和Value[]分別存儲(chǔ)鍵和值端逼。為了保證插入過程中表一直有序，對標(biāo)準(zhǔn)的二分查找稍作修改污淋，如下
public int rank(Key key) {
int low = 0;
int high = N - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) {
high = mid - 1;
} else if (cmp > 0) {
low = mid + 1;
} else {
return mid;
}
}
return low;
}
倒數(shù)第二行顶滩，未命中時(shí)原來返回-1，現(xiàn)在返回low——恰好是小于參數(shù)Key的鍵的數(shù)量寸爆，說得直白些就是在key之前的鍵的數(shù)量礁鲁。
插一句，二分查找的思想：首先查找的數(shù)組必須是有序的赁豆。先將被查找的鍵與數(shù)組中的中間鍵比較（如果表長度為偶數(shù)則會(huì)向下取整）仅醇，若小于中間的鍵就在中間鍵的左邊子數(shù)組繼續(xù)查找然遏；若大于中間的鍵就在中間鍵的右邊子數(shù)組中繼續(xù)查找杖们；否則就是查找成功了默怨。如此迭代捺萌，直到high > low終止农猬。
查找成功時(shí)返回的是mid闸迷，說明該鍵在數(shù)組中的位置就是keys[mid]教沾，小于該key的鍵的數(shù)量就是mid沾瓦，這個(gè)很好理解心铃。但為什么查找失敗最后high > low迭代終止時(shí)准谚，返回low就是小于key的鍵的數(shù)量呢？
因?yàn)椴檎沂∏埃?strong>最后查找范圍一定是只有一個(gè)元素了去扣，此時(shí)low = high = mid柱衔， 最后一次比較后發(fā)現(xiàn)也不相等，它要么比mid大愉棱，要么比mid小唆铐。如果它比mid小說明它應(yīng)該在mid的前一個(gè)位置，比它小的鍵的數(shù)量和比mid小的數(shù)量是一樣的奔滑，再看代碼中：if分支low沒有改變艾岂，返回的low和mid值一樣；如果它比mid大說明它應(yīng)該在mid的后一個(gè)位置朋其，比它小的鍵的數(shù)量應(yīng)該比小于mid的鍵的數(shù)量多1（比mid大王浴，所以把mid也算進(jìn)去）脆炎，再看代碼中：else分支low變成了mid + 1，最后返回的low實(shí)際也是mid + 1氓辣。由此驗(yàn)證了秒裕，這樣實(shí)現(xiàn)的二分查找可以返回?cái)?shù)組中小于給定key的鍵的數(shù)量！
看圖加深理解：先看查找成功時(shí)钞啸，對P查找几蜻。最后一步查找，mid=6体斩，此時(shí)命中并退出梭稚。表示P在keys[]中的位置是6，同時(shí)也表示小于P的鍵的數(shù)量為6絮吵；再看查找Q時(shí)的查找失敗哨毁。最后一步查找時(shí)，和查找P一樣low = high = mid = 6源武，只不過這次并不是返回mid扼褪，查找的Q大于mid位置的P，會(huì)執(zhí)行else if分支粱栖，Q的位置應(yīng)該在圖中第二個(gè)紅色箭頭處话浇，返回的low實(shí)際上等于mid + 1 = 7，結(jié)合圖中闹究，Q的位置之前確實(shí)有7個(gè)鍵幔崖。
上述rank方法是全部實(shí)現(xiàn)的核心，現(xiàn)在給出全部代碼渣淤，再解釋其中一些方法赏寇。
package Chap8;
import java.util.*;
public class BinarySearchST<Key extends Comparable<Key>, Value> {
private Key[] keys = (Key[]) new Comparable[1];
private Value[] values = (Value[]) new Object[1];
private int N;
public int rank(Key key) {
int low = 0;
int high = N - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0) {
high = mid - 1;
} else if (cmp > 0) {
low = mid + 1;
} else {
return mid;
}
}
return low;
}
public void put(Key key, Value value) {
// 如果傳入null，就是刪除鍵值對
if (value == null) {
delete(key);
return;
}
// 如果容量滿了价认，增容
if (N == keys.length) {
resize(2 * keys.length);
}
int i = rank(key);
// 鍵已經(jīng)存在嗅定，新值取代舊值
if (i < N && keys[i].compareTo(key) == 0) {
values[i] = value;
return;
}
// 否則插入新的鍵值對，i及之后的元素都需要后移一個(gè)位置用踩，騰出位置i給新的鍵值對使用
for (int j = N; j > i; j--) {
keys[j] = keys[j - 1];
values[j] = values[j - 1];
}
keys[i] = key;
values[i] = value;
N++;
}
public Value get(Key key) {
if (isEmpty()) {
return null;
}
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) {
return values[i];
} else {
return null;
}
}
public Value getDefault(Key key, Value defaultValue) {
if (get(key) == null) {
return defaultValue;
} else {
return get(key);
}
}
private void resize(int max) {
Key[] tempKeys = (Key[]) new Comparable[max];
Value[] tempValues = (Value[]) new Object[max];
for (int i = 0; i < N; i++) {
tempKeys[i] = keys[i];
tempValues[i] = values[i];
}
keys = tempKeys;
values = tempValues;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public int size(Key low, Key high) {
if (high.compareTo(low) < 0) {
return 0;
} else if (contains(high)) {
return rank(high) - rank(low) + 1;
} else {
return rank(high) - rank(low);
}
}
public boolean contains(Key key) {
return get(key) != null;
}
public Key min() {
return keys[0];
}
public Key max() {
return keys[N - 1];
}
public Value deleteMin() {
return delete(min());
}
public Value delete(Key key) {
int i = rank(key);
Value value = null;
if (keys[i].compareTo(key) == 0) {
value = values[i];
for (int j = i; j < N - 1; j++) {
keys[j] = keys[j + 1];
values[j] = values[j + 1];
}
// 防止對象游離
keys[N - 1] = null;
values[N - 1] = null;
N--;
// 如果只用了總?cè)萘康乃姆种磺耍s減容量一半
if (N > 0 && N == keys.length / 4) {
resize(keys.length / 2);
}
}
return value;
}
public Value deleteMax() {
return delete(max());
}
// k = rank(select(k))
// key = select(rank(key)
public Key select(int k) {
return keys[k];
}
public Set<Key> keys() {
return keys(min(), max());
}
public Collection<Value> values() {
return values(min(), max());
}
public Collection<Value> values(Key low, Key high) {
Collection<Value> q = new ArrayList<>();
for (int j = rank(low); j < rank(high); j++) {
q.add(values[j]);
}
if (contains(high)) {
q.add(values[rank(high)]);
}
return q;
}
public Set<Key> keys(Key low, Key high) {
// 保持原來的順序，使用LinkedHashSet
Set<Key> q = new LinkedHashSet<>();
for (int j = rank(low); j < rank(high); j++) {
q.add(keys[j]);
}
if (contains(high)) {
q.add(keys[rank(high)]);
}
return q;
}
// 大于等于key的最小鍵脐彩，如果key在表中就是等于key碎乃；否則是大于key的最小鍵，即i的下一個(gè)位置的鍵
public Key ceiling(Key key) {
int i = rank(key);
// i可能等于N惠奸，此時(shí)返回null梅誓，也符合
return keys[i];
}
// 小于等于key的最大鍵
public Key floor(Key key) {
int i = rank(key);
if (contains(key)) {
return keys[i];
// 考慮負(fù)數(shù)腳標(biāo)的情況，i == 0會(huì)造成keys[-1]
} else if (!contains(key) && i != 0) {
return keys[i - 1];
} else {
// 表中不沒有鍵key且i == 0，說明key是表中最小的梗掰，不存在比它還小的所以返回null
return null;
}
}
@Override
public String toString() {
if (isEmpty()) {
return "{}";
}
StringBuilder sb = new StringBuilder();
sb.append("{");
int i = 0;
while (true) {
sb.append(keys[i]).append("=").append(values[i]);
if (i == N - 1) {
return sb.append("}").toString();
} else {
sb.append(", ");
}
i++;
}
}
public static void main(String[] args) {
BinarySearchST<Integer, Double> st = new BinarySearchST<>();
st.put(1, 5567.5);
st.put(5, 10000.0);
st.put(3, 4535.5);
st.put(7, 7000.0);
st.put(12, 2500.0);
st.put(10, 4500.0);
st.put(17, 15000.5);
st.put(15, 12000.5);
st.deleteMax(); // 17
st.deleteMin(); // 1
st.delete(12); // 剩下[3, 5, 7, 10, 15]
System.out.println("符號(hào)表的長度為" + st.size());
System.out.println("[3, 6]之間有" + st.size(3, 6) + "個(gè)鍵");
System.out.println("比9小的鍵的數(shù)量為" + st.rank(9));
System.out.println("排在第4位置的鍵為" + st.select(4));
System.out.println("大于等于8的最小鍵為" + st.ceiling(8));
System.out.println("小于等于8的最大鍵為" + st.floor(8));
System.out.println("符號(hào)表所有的鍵和對應(yīng)的值為：" + st.keys() + " -> " + st.values());
System.out.println("鍵2和鍵8之間的所有鍵及對應(yīng)的值：" + st.keys(2, 8) + " -> " + st.values(2, 8));
System.out.println(st);
}
}
首先這個(gè)符號(hào)表是容量自適應(yīng)的删豺，實(shí)現(xiàn)見resize方法。這意味著我們不用擔(dān)心數(shù)組腳標(biāo)越界愧怜。思路是：當(dāng)鍵值對個(gè)數(shù)等于數(shù)組長度時(shí)候，將數(shù)組長度擴(kuò)充到原來的兩倍妈拌；當(dāng)鍵值對個(gè)數(shù)過少拥坛，等于數(shù)組長度的四分之一時(shí)，將數(shù)組長度減小到原來的一半尘分。
然后是很重要的方法get / put猜惋，put之前需要判斷是否傳入了null值，以及是否需要增容培愁，之后使用int i = rank(key)方法定位key的位置著摔，如果key在符號(hào)表中存在，會(huì)用新的值取代舊的值定续；否則在位置i處插入新的鍵值對谍咆，為此需要將i及其之后的元素都往后移動(dòng)一個(gè)位置。get方法就很簡單了私股，首先要判斷是不是空表摹察，因?yàn)橄旅嬲{(diào)用了keys[i].compareTo(key)，如果是空表倡鲸，則keys[i]是null供嚎，調(diào)用compareTo會(huì)出現(xiàn)異常。int i = rank(key)返回的i最小就是0了峭状，所以if里只需判斷i < N以防止keys[i]越界克滴。
delete方法其實(shí)就是刪除數(shù)組中某個(gè)元素，用int i = rank(key)快速定位到key的位置（如果key不在符號(hào)表中优床，刪除失敗返回null）劝赔，i之后的元素都往前移動(dòng)一個(gè)位置，最后原數(shù)組的最后一個(gè)鍵值對keys[N -1]和values[N -1]需要置空（因?yàn)樗鼈儸F(xiàn)在都往前移動(dòng)一個(gè)位置了胆敞，這個(gè)位置已經(jīng)沒有作用了）望忆，隨之N減少1表示刪除一個(gè)鍵值對成功。
min / max返回最小的鍵和最大的鍵竿秆，由于鍵數(shù)組本身有序启摄，keys[0]和keys[N - 1]就分別對應(yīng)著最小 / 最大鍵。
deleteMin / deleteMax幽钢，就是刪除最小 / 最大的鍵并返回對應(yīng)的值歉备。
select(int k)返回位置排在k的鍵。注意匪燕，細(xì)心觀察可以發(fā)現(xiàn)select和rank之間滿足如下關(guān)系蕾羊。
k = rank(select(k))
key = select(rank(key)
floor(Key key)返回小于等于key的最大鍵喧笔。還是先用int i = rank(key)定位key的位置，如果key在符號(hào)表中龟再，直接返回keys[i]书闸；否則，我們返回的應(yīng)該是keys[i - 1]利凑，這個(gè)在紙上畫畫就能理解了浆劲。有點(diǎn)要注意，如果rank(key)返回的是0哀澈，那么使用keys[i - 1]就會(huì)異常牌借，所以對i == 0單獨(dú)判斷下，此時(shí)應(yīng)該返回null割按，因?yàn)楸碇腥我怄I都沒有給出的key要小膨报。
ceiling(Key key)返回大于等于key的最小鍵，同樣如果key在符號(hào)表中适荣，直接返回keys[i]现柠；如果不在符號(hào)表中，還是應(yīng)該返回keys[i]（紙上畫畫吧）弛矛。
最后我們來看看比較有意思的size(Key low, Key high) / keys(Key low, Key high) 晒旅，還有個(gè)values(Key low, Key high)原理和keys一樣，這里就說前述兩個(gè)汪诉。這些方法都有判斷Key high在不在符號(hào)表中废恋，這有影響嗎？我們結(jié)合幾個(gè)圖來看看扒寄。
無非是下面4種情況鱼鼓。
可見當(dāng)Key high存在于符號(hào)表中時(shí)，計(jì)算size需要進(jìn)行+1操作该编，將high這個(gè)鍵也算進(jìn)去迄本；計(jì)算keys的時(shí)候也要將Key high算進(jìn)去。
由于是數(shù)組實(shí)現(xiàn)的课竣，插入和刪除都是相當(dāng)麻煩的嘉赎，不過查找效率很高。上面鏈表實(shí)現(xiàn)的順序查找于樟，在插入和刪除上有優(yōu)勢公条，但是查找效率挺低的。有沒有辦法整合這兩者的優(yōu)點(diǎn)呢迂曲？這就是接下來要學(xué)習(xí)的二叉查找樹（BST）靶橱。
by @sunhaiyu
2017.10.13
