查找----基于有序数组
参照数据结构--符号表API实现。
有序数组实现有序的符号表，使用一对平行的数组，一个保存键，一个保存值。键和值分别保存在两个数组的相同下标下，例如一个键值对，键保存在key3中，值就保存在val3中。这样，当我们查找时，找到键在key中的位置，就可以用下标去val[]数组中取到相应的值。而且，我们让Comparable类型的键有序，这样就可以用二分查找快速地在key数组中查找相应的键。
核心方法是rank()方法，它返回表中小于给定键的数量。只要给定的键在数组中，rank()方法就能精确的告诉我们去哪里找到它。因为把数组实现为有序的，所以可以通过二分查找来高效实现rank()方法。非递归方法和递归方法实现如下：
//非递归算法
public int rank(Key key) {
int lo = 0, hi = N-1;
while(lo<=hi) {
int mid = lo + (hi-lo)/2;
int cmp = key.compareTo(keys[mid]);
if(cmp<0) hi = mid-1;
if(cmp>0) lo = mid+1;
else return mid;
}
return lo;
}
//递归算法
public int rank(Key key, int lo, int hi) {
if(hi<lo) return lo;
int mid = lo + (hi-lo)/2;
int cmp = key.compareTo(keys[mid]);
if(cmp<0) return rank(key,lo,hi-1);
if(cmp>0) return rank(key,mid+1,hi);
else return mid;
}在有了rank()方法后，get()方法很好实现。对于get()方法，只要给定的键存在，rank()方法能够精确给出目标下标；如果找不到，就是不存在。get()方法实现如下：
public Value get(Key key) {
if(isEmpty()) return null;
int i = rank(key);
if(i<N&&keys[i].compareTo(key)==0) return vals[i];
else return null;
}对于put()方法，如果键存在，则要更新，rank()方法返回到哪里去更新；如果键不存在，则要插入，rank()方法给出在哪里插入；插入方法和数组排序算法相同，将所有更大的键先向后移动，然后把目标键值对插入相应位置。put()方法实现如下：
public void put(Key key,Value val) {
int i = rank(key);
if(i<N&&keys[i].compareTo(key)==0) {
vals[i] = val;return;
}
for(int j = N; j>i;j--) {
keys[j] = keys[j-1];vals[j] = vals[j-1];
}
keys[i] = key;vals[i] = val;
N++;
}对于delete()方法，rank()返回要删除键值对的下标，然后将更大的键值对向前移一位即可：
public void delete(Key key) {//删除
if(isEmpty()) return;
int i = rank(key);
if(key.compareTo(keys[i])==0) {
for(int j = i;j<N;j++) {
keys[j] = keys[j+1];vals[j] = vals[j+1];
N--;
}
}
else return;
}- 其他方法也都容易实现，其实都是在调用rank()方法。
- 在N个键的有序数组中进行二分查找最多需要（lgN+1)次比较（无论是否成功）。
- 向大小为N的有序数组中插入新元素最坏情况需要访问~2N次数组，所以构造一个N元素符号表需要访问~N^2次数组。
可以看出，基于有序数组实现符号表，查询操作效率提高了，但插入效率比较差。要高效支持插入操作，似乎需要一种链式结构，能够同时满足条件的就是二叉查找树。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读