浅谈算法和数据结构: 六 符号表及其基本实现(二)
/// 如果存在相等的key，则直接更新value，否则将该key，value插入到合适的位置
/// 1.首先将该位置往后的元素都往后移以为
/// 2.然后再讲该元素放到为i的位置上
///
///
///
public override void Put(TKey key, TValue value)
{
int i = Rank(key);
if (i < length && keys[i].Equals(key))
{
values[i] = value;
return;
}
//如果长度相等，则扩容
if (length == keys.Length) Resize(2 * keys.Length);
for (int j = length; j > i; j--)
{
keys[j] = keys[j - 1];
values[j] = values[j - 1];
}
keys[i] = key;
values[i] = value;
length++;
}
///
/// 返回key在数组中的位置
///
///
///
private int Rank(TKey key)
{
int lo = 0;
int hi = length - 1;
while (lo <= hi)
{
int mid = lo + (hi - lo) / 2;
if (key.CompareTo(keys[mid]) > 0) lo = mid + 1;
else if (key.CompareTo(keys[mid]) < 0) hi = mid - 1;
else return mid;
}
return lo;
}
。。。
}
这里面重点是Rank方法，我们可以看到首先获取mid位置，然后将当前元素和mid位置元素比较，然后更新lo或者hi的位置用mid来替换，如果找到相等的，则直接返回mid，否则返回该元素在集合中应该插入的合适位置。上面是使用迭代的方式来实现的，也可以改写为递归：
private int Rank(TKey key, int lo, int hi)
{
if (lo >= hi) return lo;
int mid = lo + (hi - lo) / 2;
if (key.CompareTo(keys[mid]) > 0)
return Rank(key, mid + 1, hi);
else if (key.CompareTo(keys[mid]) < 0)
return Rank(key, lo, hi - 1);
else
return mid;
}