一符號表
在開始介紹查找算法之前，我們需要定義一個名為符號表（Symbol Table）的抽象數據結構，該數據結構類似我們再C#中使用的Dictionary，他是對具有鍵值對元素的一種抽象，每一個元素都有一個key和value，我們可以往里面添加key，value鍵值對，也可以根據key來查找value。在現實的生活中，我們經常會遇到各種需要根據key來查找value的情況，比如DNS根據域名查找IP地址，圖書館根據索引號查找圖書等等：
SymbolTableApplication
為了實現這一功能，我們定義一個抽象數據結構，然后選用合適的數據結構來實現：
public class ST
ST()
創建一個查找表對象
void Put(Key key, Value val)
往集合中插入一條鍵值對記錄，如果value為空，不添加
Value Get(Key key)
根據key查找value，如果沒找到返回null
void Delete(Key key)
刪除鍵為key的記錄
boolean Contains(Key key)
判斷集合中是否存在鍵為key的記錄
boolean IsEmpty()
判斷查找表是否為空
int Size()
返回集合中鍵值對的個數
Iterable
返回集合中所有的鍵
二實現
1 使用無序鏈表實現查找表
查找表的實現關鍵在于數據結構的選擇，最簡單的一種實現是使用無序鏈表來實現，每一個節點記錄key值，value值以及指向下一個記錄的對象。
SymbolTableImplementByUnOrderedLinkList
如圖，當我們往鏈表中插入元素的時候，從表頭開始查找，如果找到，則更新value，否則，在表頭插入新的節點元素。
實現起來也很簡單：
public class SequentSearchSymbolTable
{
private int length = 0;
Node first;
private class Node
{
public TKey key { get; set; }
public TValue value { get; set; }
public Node next { get; set; }
public Node(TKey key, TValue value, Node next)
{
this.key = key;
this.value = value;
this.next = next;
}
}
public override TValue Get(TKey key)
{
TValue result = default(TValue);
Node temp = first;
while (temp != null)
{
if (temp.key.Equals(key))
{
result = temp.value;
break;
}
temp = temp.next;
}
return result;
}
public override void Put(TKey key, TValue value)
{
Node temp = first;
while (temp != null)
{
if (temp.key.Equals(key))
{
temp.value = value;
return;
}
temp = temp.next;
}
first = new Node(key, value, first);
length++;
}
....
}
分析：
從圖或者代碼中分析可知，插入的時候先要查找，如果存在則更新value，查找的時候需要從鏈表頭進行查找，所以插入和查找的平均時間復雜度均為O(n)。那么有沒有效率更好的方法呢，下面就介紹二分查找。
2 使用二分查找實現查找表
和采用無序鏈表實現不同，二分查找的思想是在內部維護一個按照key排好序的二維數組，每一次查找的時候，跟中間元素進行比較，如果該元素小，則繼續左半部分遞歸查找，否則繼續右半部分遞歸查找。整個實現代碼如下：
class BinarySearchSymbolTable
{
private TKey[] keys;
private TValue[] values;
private int length;
private static readonly int INIT_CAPACITY = 2;
public BinarySearchSymbolTable(int capacity)
{
keys = new TKey[capacity];
values = new TValue[capacity];
length = capacity;
}
public BinarySearchSymbolTable() : this(INIT_CAPACITY)
{
}
///
/// 根據key查找value。
/// 首先查找key在keys中所處的位置，如果在length范圍內，且存在該位置的值等于key，則返回值
/// 否則，不存在
///
///
///
public override TValue Get(TKey key)
{
int i = Rank(key);
if (i < length && keys[i].Equals(key))
return values[i];
else
return default(TValue);
}
///
/// 向符號表中插入key，value鍵值對。
/// 如果存在相等的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;
}