對半搜索是一種二分搜索, 將表劃分為長度幾乎相等的兩個子表. 共有函數Search()調用私有函數BSearch(). 而后遞歸調用BSearch()函數實現對有序表的對半搜索. mid, left, right均為元素下標, 如果當前表不為空, 則令x與l[mid]比較. 若兩者相等, 則搜索成功. 若前者小于后者, 則繼續查找左半部分, 否則查找右半部分. 下標范圍分別為[left, mid - 1], [mid + 1, right]. 如果當前搜索表為空表, 搜索失敗返回NotPresent. 實現代碼: ~~~ #include "iostream" #include "cstdio" #include "cstring" #include "algorithm" #include "assert.h" using namespace std; const int MAXN = 9999; enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent }; template <class T> class DynamicSet { public: virtual ResultCode Search(T &x) const = 0; // 表中搜索與x關鍵字相同的元素, 若存在則賦值給x并且返回Success, 否則返回NotPresent virtual ResultCode Insert(T &x) = 0; // 表中搜索與x關鍵字相同的元素, 若存在該元素, 賦值給x返回Duplicate, 若表已滿返回Overflow, 若表未滿返回Success virtual ResultCode Remove(T &x) = 0; // 表中搜索與x關鍵字相同的元素, 若存在該元素, 賦值給x返回Success, 否則返回NotPresent virtual bool IsEmpty() const = 0; // 集合為空返回true virtual bool IsFull() const = 0; // 集合為滿返回true /* data */ }; template <class T> class ListSet: public DynamicSet<T> { public: ListSet( int mSize ); ~ListSet() { delete []l; } bool IsEmpty() const { return n == 0; } bool IsFull() const { return n == maxSize; } ResultCode Search(T &x) const; ResultCode Insert(T &x); ResultCode Remove(T &x); void Print(); private: T *l; int maxSize, n; int BSearch(T &x, int left, int right) const; /* data */ }; template <class T> void ListSet<T>::Print() { for(int i = 0; i < n; ++i) cout << l[i] << "\t"; cout << endl; } template <class T> ListSet<T>::ListSet(int mSize) { maxSize = mSize; l = new T[maxSize]; n = 0; } template <class T> ResultCode ListSet<T>::Insert(T &x) { assert(!IsFull()); l[n++] = x; l[n] = MAXN; return Success; } template <class T> ResultCode ListSet<T>::Remove(T &x) { } template <class T> ResultCode ListSet<T>::Search(T &x) const { int i = BSearch(x, 0, n - 1); if(i == -1) return NotPresent; x = l[i]; return Success; } template <class T> int ListSet<T>::BSearch(T &x, int left, int right) const { if(left <= right) { int mid = (left + right) / 2; if(x < l[mid]) return BSearch(x, left, mid - 1); else if(x > l[mid]) return BSearch(x, mid + 1, right); else return mid; } return -1; } int main(int argc, char const *argv[]) { ListSet<int> ls(20); int x = 21; ls.Insert(x); x = 30; ls.Insert(x); x = 36; ls.Insert(x); x = 41; ls.Insert(x); x = 52; ls.Insert(x); x = 54; ls.Insert(x); x = 66; ls.Insert(x); x = 72; ls.Insert(x); x = 83; ls.Insert(x); x = 97; ls.Insert(x); ls.Print(); x = 66; if(ls.Search(x) == Success) cout << "Found " << x << endl; else cout << "Not Found " << x << endl; return 0; } ~~~