数据结构与算法--查找之顺序查找和二分查找
数据结构与算法--查找之顺序查找和二分查找
符号表的目的是将一个键和一个值关联起来，可以将一对键值对插入到符号表中，也可以根据给定的键从符号表所有的键值对中快速或者直接找到相对应的值。对于键和值，我们作如下约定，以后的实现都遵循这些约定。
- 每个键只对应一个值，也就是说不允许存在重复的键
- 新插入的键值对在表中键已经存在，此时称为冲突，让新的值取代旧的值
- 键不能为空null，因为在比较中会调用键的equals或者compareTo方法；若为空会造成空指针异常
- 值不能为空null，因为在我们的实现中，当查找一个不存在的键时，默认返回null。因此我们可以用
get(Key key)判断某个键在表中是否存在；也可以用put(Key key, null)将某键值对删除（延时实现）。
无序链表的顺序查找
顺序查找也就是遍历表中元素，链表实现即每个结点都表示一个键值对。如get(Key key)方法，查找表中所有键值对，如果匹配成功就返回相应的值，否则返回null；put(Key key, Value value)方法也是查找表中所有键值对，如果键已经存在就更新值，否则在链表头插入这个新的键值对。实现起来很简单，我们来看代码。
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;
}
// 若是键不存在，则返回一个指定的默认值
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++;
}
// 未采用的延时删除，使用下面的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 {
// 现在pre是first，而cur是first的下一个结点
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;
}
// 下轮比较指向下一个结点，所以更新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方法没什么好说的，有一个getDefault方法，当给出的键不存在时，将返回一个由调用者自定义的默认值。put方法中，如果值传入null，相当于是删除该键值对，所以调用了delete。否则遍历链表，如果查找到键已经存在，则用新的value取代旧的value；如果没找到，说明这是新的键值对，直接插入到链表头（相当于push操作）。
重点看delete方法，我们并不打算用延时实现——虽然它相当简单。如下
public void delete(Key key) {
put(key, null);
}
注意：如果使用上述实现，put方法头几行判断就得去掉，否则两个方法会互相调用导致StackOverflow。我们的实现是即时删除的，其实就是链表删除结点的操作。即时delete中，需要一个Node pre指针，用于指向当前结点的前一个结点，如果你对链表结点的删除操作熟悉的话，应该清楚为什么需要这个pre指针。链表头的删除和其他地方结点的删除操作还有些不一样：删除链表头只需first.next成为新的first；其他位置的删除，删除的是结点cur，需要将cur的前一个结点pre的next指向cur的next，即pre.next = cur.next。
keys和values方法可以返回符号表中所有的键值对，键是唯一的所以用了Set存放。
在含有N对键值对的无序链表中，未命中和插入新键值对的比较次数均为N，命中的最坏情况为比较N次（最后一个结点才匹配成功）。
有序数组中的二分查找
上面链表实现的符号表中，表是无序的。如果能在插入过程中保证表一直有序，在查找的时候就不必顺序查找，使用二分查找可大大提高查找的效率。我们需要两个数组，Key[]和Value[]分别存储键和值。为了保证插入过程中表一直有序，对标准的二分查找稍作修改，如下
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;
}
倒数第二行，未命中时原来返回-1，现在返回low——恰好是小于参数Key的键的数量，说得直白些就是在key之前的键的数量。
插一句，二分查找的思想：首先查找的数组必须是有序的。先将被查找的键与数组中的中间键比较（如果表长度为偶数则会向下取整），若小于中间的键就在中间键的左边子数组继续查找；若大于中间的键就在中间键的右边子数组中继续查找；否则就是查找成功了。如此迭代，直到high > low终止。
查找成功时返回的是mid，说明该键在数组中的位置就是keys[mid]，小于该key的键的数量就是mid，这个很好理解。但为什么查找失败最后high > low迭代终止时，返回low就是小于key的键的数量呢？
因为查找失败前，最后查找范围一定是只有一个元素了，此时low = high = mid， 最后一次比较后发现也不相等，它要么比mid大，要么比mid小。如果它比mid小说明它应该在mid的前一个位置，比它小的键的数量和比mid小的数量是一样的，再看代码中：if分支low没有改变，返回的low和mid值一样；如果它比mid大说明它应该在mid的后一个位置，比它小的键的数量应该比小于mid的键的数量多1（比mid大，所以把mid也算进去），再看代码中：else分支low变成了mid + 1，最后返回的low实际也是mid + 1。由此验证了，这样实现的二分查找可以返回数组中小于给定key的键的数量！
看图加深理解：先看查找成功时，对P查找。最后一步查找，mid=6，此时命中并退出。表示P在keys[]中的位置是6，同时也表示小于P的键的数量为6；再看查找Q时的查找失败。最后一步查找时，和查找P一样low = high = mid = 6，只不过这次并不是返回mid，查找的Q大于mid位置的P，会执行else if分支，Q的位置应该在图中第二个红色箭头处，返回的low实际上等于mid + 1 = 7，结合图中，Q的位置之前确实有7个键。
上述rank方法是全部实现的核心，现在给出全部代码，再解释其中一些方法。
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);
// 键已经存在，新值取代旧值
if (i < N && keys[i].compareTo(key) == 0) {
values[i] = value;
return;
}
// 否则插入新的键值对，i及之后的元素都需要后移一个位置，腾出位置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--;
// 如果只用了总容量的四分之一，缩减容量一半
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的下一个位置的键
public Key ceiling(Key key) {
int i = rank(key);
// i可能等于N，此时返回null，也符合
return keys[i];
}
// 小于等于key的最大键
public Key floor(Key key) {
int i = rank(key);
if (contains(key)) {
return keys[i];
// 考虑负数脚标的情况，i == 0会造成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("符号表的长度为" + st.size());
System.out.println("[3, 6]之间有" + st.size(3, 6) + "个键");
System.out.println("比9小的键的数量为" + 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("符号表所有的键和对应的值为：" + st.keys() + " -> " + st.values());
System.out.println("键2和键8之间的所有键及对应的值：" + st.keys(2, 8) + " -> " + st.values(2, 8));
System.out.println(st);
}
}
首先这个符号表是容量自适应的，实现见resize方法。这意味着我们不用担心数组脚标越界。思路是：当键值对个数等于数组长度时候，将数组长度扩充到原来的两倍；当键值对个数过少，等于数组长度的四分之一时，将数组长度减小到原来的一半。
然后是很重要的方法get / put，put之前需要判断是否传入了null值，以及是否需要增容，之后使用int i = rank(key)方法定位key的位置，如果key在符号表中存在，会用新的值取代旧的值；否则在位置i处插入新的键值对，为此需要将i及其之后的元素都往后移动一个位置。get方法就很简单了，首先要判断是不是空表，因为下面调用了keys[i].compareTo(key)，如果是空表，则keys[i]是null，调用compareTo会出现异常。int i = rank(key)返回的i最小就是0了，所以if里只需判断i < N以防止keys[i]越界。
delete方法其实就是删除数组中某个元素，用int i = rank(key)快速定位到key的位置（如果key不在符号表中，删除失败返回null），i之后的元素都往前移动一个位置，最后原数组的最后一个键值对keys[N -1]和values[N -1]需要置空（因为它们现在都往前移动一个位置了，这个位置已经没有作用了），随之N减少1表示删除一个键值对成功。
min / max返回最小的键和最大的键，由于键数组本身有序，keys[0]和keys[N - 1]就分别对应着最小 / 最大键。
deleteMin / deleteMax，就是删除最小 / 最大的键并返回对应的值。
select(int k)返回位置排在k的键。注意，细心观察可以发现select和rank之间满足如下关系。
k = rank(select(k))
key = select(rank(key)
floor(Key key)返回小于等于key的最大键。还是先用int i = rank(key)定位key的位置，如果key在符号表中，直接返回keys[i]；否则，我们返回的应该是keys[i - 1]，这个在纸上画画就能理解了。有点要注意，如果rank(key)返回的是0，那么使用keys[i - 1]就会异常，所以对i == 0单独判断下，此时应该返回null，因为表中任意键都没有给出的key要小。
ceiling(Key key)返回大于等于key的最小键，同样如果key在符号表中，直接返回keys[i]；如果不在符号表中，还是应该返回keys[i]（纸上画画吧）。
最后我们来看看比较有意思的size(Key low, Key high) / keys(Key low, Key high) ，还有个values(Key low, Key high)原理和keys一样，这里就说前述两个。这些方法都有判断Key high在不在符号表中，这有影响吗？我们结合几个图来看看。
无非是下面4种情况。
可见当Key high存在于符号表中时，计算size需要进行+1操作，将high这个键也算进去；计算keys的时候也要将Key high算进去。
由于是数组实现的，插入和删除都是相当麻烦的，不过查找效率很高。上面链表实现的顺序查找，在插入和删除上有优势，但是查找效率挺低的。有没有办法整合这两者的优点呢？这就是接下来要学习的二叉查找树（BST）。
by @sunhaiyu
2017.10.13
