前言

符号表是一种存储键值对的数据结构，可以支持高效地插入、查找等操作，因此在这里使用一个有序符号表接口来定义这些操作，这个符号表将保持键的有序性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public interface OrderedST<Key extends Comparable<Key>, Value> {

    int size();

    void put(Key key, Value value);

    Value get(Key key);

    Key min();

    Key max();

    int rank(Key key);

    List<Key> keys(Key l, Key h);
}

二分查找

二分查找先将被查找的键和数组的中间键比较，如果被查找的键小于中间键，我们就在左子数组中继续查找，如果大于我们就在右子数组中继续查找，否则中间键就是我们要找的键。如果表中存在该键，此方法将返回该键的位置，否则，将返回该键应该插入的位置。

二分查找有很多种不同的实现方式，但个人更加喜欢用以下的方式实现，这同时也是书上的实现方式：

1
2
3
4
5
6
7
8
9
10
11
public int binarySearch(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + (high - low) / 2;
		if(nums[mid] < target) low = mid + 1;
		else if(nums[mid] > target) high = mid - 1;
		else return mid;
	}
	return low;
}

查找数字第一次出现的位置

对二分查找可以做一个简单的拓展，即当一个有序数组中有重复的数字时，查找一个数字在数组中第一次出现的位置。例如，对于数组{1, 2, 3, 3, 3, 3, 4}，要查找的数字3的下标应该为2而不是3。我们仅仅需要对普通的二分查找算法做一个简单的修改就能完成此功能：

1
2
3
4
5
6
7
8
9
10
public int binarySearchFirst(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + (high - low) / 2;
		if(nums[mid] < target) low = mid + 1;
		else if(nums[mid] >= target) high = mid - 1;
	}
	return low;
}

查找数字最后一次出现的位置

同理，我们也可以使用二分查找找到重复数字在有序数组中最后一次出现的位置：

1
2
3
4
5
6
7
8
9
10
public int binarySearchLast(int[] nums, int target) {
	int low = 0;
	int high = nums.length - 1;
	while(low <= high) {
		int mid = low + (high - low) / 2;
		if(nums[mid] <= target) low = mid + 1;
		else if(nums[mid] > target) high = mid - 1;
	}
	return high;
}

二分查找实现有序符号表

使用一对平行数组，分别用来存储键和值。

这份实现的核心是rank()方法，它几乎和上面单独列出的二分查找法一样，返回找到的键的位置或者键应该插入的位置。对于put()方法，如果键存在于表中则更新它的值，否则插入到合适的位置，并将所有更大的键向后移动一格。get()方法根据rank()方法的返回值来取键相应的值，如果不存在则返回null。

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class BinarySearchOrderedST<Key extends Comparable<Key>, Value> implements OrderedST<Key, Value> {

    private Key[] keys;
    private Value[] values;
    private int N = 0;

    public BinarySearchOrderedST(int capacity) {
        keys = (Key[]) new Comparable[capacity];
        values = (Value[]) new Object[capacity];
    }

    @Override
    public int size() {
        return N;
    }
    
    @Override
    public int rank(Key key) {
        int l = 0, h = N - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            int cmp = key.compareTo(keys[m]);
            if (cmp == 0)
                return m;
            else if (cmp < 0)
                h = m - 1;
            else
                l = m + 1;
        }
        return l;
    }

    @Override
    public List<Key> keys(Key l, Key h) {
        int index = rank(l);
        List<Key> list = new ArrayList<>();
        while (keys[index].compareTo(h) <= 0) {
            list.add(keys[index]);
            index++;
        }
        return list;
    }

    @Override
    public void put(Key key, Value value) {
        int index = rank(key);
        if (index < N && keys[index].compareTo(key) == 0) {
            values[index] = value;
            return;
        }
        for (int j = N; j > index; j--) {
            keys[j] = keys[j - 1];
            values[j] = values[j - 1];
        }
        keys[index] = key;
        values[index] = value;
        N++;
    }

    @Override
    public Value get(Key key) {
        int index = rank(key);
        if (index < N && keys[index].compareTo(key) == 0)
            return values[index];
        return null;
    }

    @Override
    public Key min() {
        return keys[0];
    }

    @Override
    public Key max() {
        return keys[N - 1];
    }
}

复杂度分析

二分查找的时间复杂度是对数级别的，故使用二分查找实现的符号表的查找操作所需要的时间也是对数级别的，但是插入操作由于需要移动数组元素，因此是线性级别的。

参考资料