順序查找(基于無序鏈表)
``` public class SequentialSearchST {
private Node first;
private class Node {
//鏈表結(jié)點的定義
Key key;
Value val;
Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next; }
}
public Value get(Key key) {
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key)) //擊中
return x.val;
return null; }
public void put(Key key,Value val){
for (Node x=first;x!=null;x=x.next){
if (key.equals(x.key)){//命中 ,更新
x.val=val; }
first=new Node(key,val,first);//未命中捆姜,新建結(jié)點 }
}
```
基于有序數(shù)組
```
public class BinarySearchST< Key extends Comparable<Key>,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 rank1(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 rank1(key, lo, mid - 1); }
else if (cmp > 0) {
return rank1(key, mid + 1, hi); }
else
return mid;
}
//二分查找(迭代)
public int rank2(Key key) {
int lo = 0, hi = N - 1;
if (hi < lo)
return lo;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0)
hi = mid - 1;
else if (cmp > 0)
lo = mid + 1;
else
return mid; }
return lo; }
}
完美散花好港,謝謝吏够。