秩序あるkey-valueの値と保存の実装
1583 ワード
package find;
/**
* @author: jian.tang
* @description:
* @date: 2019/5/20 16:40
*/
public class BinarySearchST,Value> {
private Key [] keys;
private Value [] values;
private int N;
private BinarySearchST(int capacity)
{
keys = (Key[]) new Comparable[capacity];
values = (Value[]) new Object[capacity];
}
public int size()
{ return N ;}
public boolean isEmpty(){
return N == 0;
}
//
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 void put(Key key,Value value)
{
int mid = rank(key);
if (mid < N && keys[mid].compareTo(key) == 0){
values[mid] = value;
return;
}
for (int j = N; j > mid; j --)
{
keys[j] = keys[j -1];
values[j] = values[j - 1];
}
keys[mid] = key;
values[mid] = value;
N++;
}
// key
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) return hi = mid + 1;
else if (cmp < 0) return hi = mid - 1;
else return mid;
}
return lo;
}
}