1? 二分查找

算法思想：

二分查找要求元素排列有序。首先，假設表中元素是按升序排列，將數組中間位置的元素與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將數組分成前、后兩個子數組，如果中間位置記錄的元素大于查找關鍵字，則進一步查找前一子數組，否則進一步查找后一子數組。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

二分查找的時間復雜度為O（logN)

算法實現：

遞歸算法：

//遞歸算法
public int rank(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 rank(key,lo,hi-1);if(cmp>0)	return rank(key,mid+1,hi);else return mid;
}

非遞歸算法：

//非遞歸算法
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;if(cmp>0)	lo = mid+1;else return mid;}return lo;
}

2? 二叉查找樹

定義：

二叉排序樹或者是一棵空樹，或者是具有下列性質的二叉樹：

• 若左子樹不空，則左子樹上所有結點的值均小于或等于它的根結點的值；
• 若右子樹不空，則右子樹上所有結點的值均大于或等于它的根結點的值；
• 左、右子樹也分別為二叉排序樹；

步驟：

若根結點的關鍵字值等于查找的關鍵字，成功。否則，若小于根結點的關鍵字值，遞歸查左子樹。若大于根結點的關鍵字值，遞歸查右子樹。若子樹為空，查找不成功。

二叉查找樹的時間復雜度為O（logN)

算法實現：

結點類：

private class Node{private Key key;private Value val;private Node left,right;private int N;public Node(Key key,Value val, int N) {	this.key = key; this.val = val; this.N = N; }
}

其中N為以該節點為根的子樹的節點總數，計算方法如下：

size(x) = size(x.left) + size(x.right) + 1

?查找方法：

遞歸查找，如果小于當前結點，遞歸去左子樹查找；如果大于當前結點，遞歸去右子樹查找。

public Value get(Key key) {return get(root,key);
}
public Value get(Node x,Key key) {if(x==null)return null;int cmp = key.compareTo(x.key);if(cmp<0)	return get(x.left,key);if(cmp>0)	return get(x.right,key);else return x.val;
}

插入方法：

先查找，如果樹中已經存在相應的鍵，只需更新值；如果查詢無果，指針也已經指向了應該插入的位置，用要插入的鍵值對新創結點并插入到相關位置。

public void put(Key key,Value val) {root = put(root,key,val);
}
private Node put(Node x,Key key,Value val) {if(x == null) return new Node(key,val,1);int cmp = key.compareTo(x.key);if(cmp<0)	x.left = put(x.left,key,val);//插入左子樹if(cmp>0)	x.right = put(x.right,key,val);//插入右子樹else x.val = val;//更新值x.N = size(x.left) + size(x.right)+1;return x;
}

刪除方法：

1. 即將被刪除的節點記為t
2. x指向它的后繼節點min(t.right)
3. 將x的右鏈接鏈接到x的父節點的左鏈接上（即替換掉原x的位置）
4. 用x節點替換t節點（將t.left和t.right設為x.left和x.right）

public void delete(Key key) {root = delete(root,key);
}
private Node delete(Node x,Key key) {if(x == null)	return null;int cmp = key.compareTo(x.key);if(cmp<0)	x.left = delete(x.left,key);if(cmp>0)	x.right = delete(x.right,key);else {if(x.right == null)		return x.left;if(x.left == null)		return x.right;Node t = x;x = min(t.right);x.right = deleteMin(t.right);x.left = t.left;}x.N = size(x.left)+size(x.right)+1;return x;
}

?