3.1 符号表之二分查找
一.查找
1.对于简单的查找来说，主要是顺序查找和二分查找。顺序查找主要是用无序链表来维持key，二分查找主要是用有序数组来维持。
2.对顺序查找来说，难点在于查找，而二分查找难点在于插入。
二.二分查找
1.思路：递归的rank（）满足：
（1）如果表中存在该键，rank()应该返回该键的位置，即表中小于它的键的数量
（2）如果表中不存在该键，rank()还是应该返回表中小于它的键的数量
2.二分查找的实现：
private 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; }
3.对于符号表的二分查找来说，如果keys[i]等于该值，则返回，否则返回null，即未找到
对于插入来说，如果找到了，则替换value；否则插入该值，并将后续元素向后移动一位。
package com.cx.serch; public class BinarySearchST <Key extends Comparable<Key>,Value>{ private Key[] keys; private Value[] values; private int N; public BinarySearchST(int capacity) { keys=(Key[])new Comparable[capacity]; values=(Value[])new Object[capacity]; } public int size() { return N; } private boolean isEmpty() { return N==0; } //查找 public Value get(Key key) { if(isEmpty()) return null; int i=rank(key); if(i<N && keys[i].compareTo(key)== 0) return values[i]; else return null; } //插入 public void put(Key key,Value value) { int i=rank(key); //如果找到了键，替换值 if(i<N && keys[i].compareTo(key)==0) { values[i]=value; return; } //如果没找到，在i处插入，并将较大的往后移动一位 for(int j=N;j>i;j--) { keys[j]=keys[j-1]; values[j]=values[j-1]; } keys[i]=key; values[i]=value; N++; } //返回小于给定键的键的数量,即key应该在的位置的坐标 //二分查找 private 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; } }