无序链表的顺序查找

public class SequentialSearchST
     
      {	private Node first;           //链表首结点	private class Node	{	//链表结点的定义		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; return;	}     //命中，更新		first = new Node(key, val, first);    //未命中，新建结点	}}
     

　　向一个空表插入N个不同的键需要N²/2次比较，一次查找所需比较数，采用随机命中的话是N/2，说明基于链表的实现和顺序查找是非常低效的。

有序数组中的二分查找

 

public class BinarySearchST
     
      , Value>{	private Key[] keys;	private Value[] vals;	private int N;	public BinarySearchST(int capacity)	{		keys = (Key[])  new Comparable[capacity];		vals = (value[]) new Object[capacity];	}	public int size()	{	return N;	}	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;	}	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;			else if (cmp > 0) lo = mid + 1;			else return mid;		}		return lo;	}	public void put(Key key, Value value)	{	//查找键，找到则更新值，否则创建新的元素		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++;	}	public Key min()	{	return keys[0];	}	public Key max()	{	return keys[N-1];	}	public Key select(int k)	{	return keys[k];	}	public Key ceiling(Key key)	{		int i = rank(key);		return keys[i];	}	public Key floor(Key key)	{	}	public void delete(Key key)	{		int i = rank(key);		for (int j = i; j < N-1; j++)		{	keys[j] = keys[j+1]; vals[j] = vals[j+1];	}			}	public Iterable
      
        keys(Key lo, Key hi)	{		Queue
       
         q = new Queue
        
         ();		for (int i = rank(lo); i < rank(hi); i++)			q.enqueue(keys[i]);		if (contains(hi))			q.enqueue(keys[rank(hi)]);		return q;	}}
        
       
      
     

　　N个键的有序数组进行二分查找最多需要（lgN+1）次比较。