前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。
在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。
一符号表
在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，每一个元素都有一个key和value，我们可以往里面添加key，value键值对，也可以根据key来查找value。在现实的生活中，我们经常会遇到各种需要根据key来查找value的情况，比如DNS根据域名查找IP地址，图书馆根据索引号查找图书等等：
为了实现这一功能，我们定义一个抽象数据结构，然后选用合适的数据结构来实现：
public class ST<Key, Value>
| 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<Key> Keys() | 返回集合中所有的键 |
二实现
1 使用无序链表实现查找表
查找表的实现关键在于数据结构的选择，最简单的一种实现是使用无序链表来实现，每一个节点记录key值，value值以及指向下一个记录的对象。
如图，当我们往链表中插入元素的时候，从表头开始查找，如果找到，则更新value，否则，在表头插入新的节点元素。
实现起来也很简单：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
public class SequentSearchSymbolTable<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TKey> { 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排好序的二维数组，每一次查找的时候，跟中间元素进行比较，如果该元素小，则继续左半部分递归查找，否则继续右半部分递归查找。整个实现代码如下：
|
1 2 3 4 5 6 7 8 9 解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。
一符号表在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，每一个元素都有一个key和value，我们可以往里面添加key，value键值对，也可以根据key来查找value。在现实的生活中，我们经常会遇到各种需要根据key来查找value的情况，比如DNS根据域名查找IP地址，图书馆根据索引号查找图书等等：
为了实现这一功能，我们定义一个抽象数据结构，然后选用合适的数据结构来实现： public class ST<Key, Value>
二实现1 使用无序链表实现查找表查找表的实现关键在于数据结构的选择，最简单的一种实现是使用无序链表来实现，每一个节点记录key值，value值以及指向下一个记录的对象。
如图，当我们往链表中插入元素的时候，从表头开始查找，如果找到，则更新value，否则，在表头插入新的节点元素。 实现起来也很简单：
分析： 从图或者代码中分析可知，插入的时候先要查找，如果存在则更新value，查找的时候需要从链表头进行查找，所以插入和查找的平均时间复杂度均为O(n)。那么有没有效率更好的方法呢，下面就介绍二分查找。 2 使用二分查找实现查找表和采用无序链表实现不同，二分查找的思想是在内部维护一个按照key排好序的二维数组，每一次查找的时候，跟中间元素进行比较，如果该元素小，则继续左半部分递归查找，否则继续右半部分递归查找。整个实现代码如下： |
