算法3.2 二分查找（基于有序数组）（algs4）

                                                有序泛型符号表的API

public class BinarySearchST<Key extends Comparable<Key>,Value>

private Key[] keys                                 存储键 private Value[] vals                                存储值 private int N

public BinarySearchST(int capacity)         创建一张有序符号表 public int size()                                       表中的键值对数量  public boolean isEmpty()                          表是否为空 public Value get(Key key)                         获取键 key 对应的值（若键 key 不存在则返回空）                   public int rank(Key key)                           小于key的键的数量 public void put(Key key,Value val)              查找键，找到则更新值，否则创建新的元素 public Key min()                                      最小的键 public Key max()                                     最大的键    public Key select(int k)                            排名为 k 的键 public Key ceiling(Key key)                      向上取整：大于等于key的最小键 public Key floor(Key key)                         向下取整：小于等于key的最大键 public void delete(Key key)                      从表中删去键key（及其对应的值） public void resize(int max)                        动态调整数组大小 public boolean contains(Key key)              键key是否存在于表中 public Iterable<Key> keys(Key lo,Key hi)    [lo..hi]之间的所有键，已排列

 

package _3_Searching;

import edu.princeton.cs.algs4.Queue;

/** 算法3.2 二分查找（基于有序数组）
 * 数据结构是一对平行的数组，一个存储键一个存储值。
 * 核心是 rank() 方法，它返回表中小于给定键的键的数量。
 * 需要创建一个 Key 类型的 Comparable 对象的数组和一个Value 类型的 Object 对象的数组，
 * 并在构造函数中将它们转化回 Key[] 和 Value[] 。
*/
public class BinarySearchST<Key extends Comparable<Key>,Value>
{
private Key[] keys;
private Value[] vals;
private int N;
public BinarySearchST(int capacity)
{
keys=(Key[]) new Comparable[capacity];
vals=(Value[]) new Comparable[capacity];
}
public int size()
{
return N;
}
public 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 vals[i];
else return null;
}
/*基于有序数组的二分查找*/
public int rank(Key key)/*小于key的键的数量*/
{                  /*迭代的二分查找*/
int lo=0,hi=N-1;
while(lo<=hi)
{
int mid=(lo+hi)/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;
}

public void put(Key key,Value val)
{                                        /*查找键，找到则更新值，否则创建新的元素*/
int i=rank(key);
if(i<N&&keys[i].compareTo(key)==0)
{
vals[i]=val;
return;
}
for(int j=N;j>i;j--)
{
keys[j]=keys[j-1];
vals[j]=vals[j-1];
}
keys[i]=key;
vals[i]=val;
N++;
if(N==keys.length)
resize(2*keys.length);
}
public Key min()
{
return keys[0];
}
public Key max()
{
return keys[N-1];
}
public Key select(int k)
{
return keys[k];
}
public Key ceiling(Key key)/*向上取整：大于等于key的最小键*/
{
int i=rank(key);
return keys[i];
}
public Key floor(Key key)/*向下取整：小于等于key的最大键*/
{
int i=rank(key);
if(i<N&&key.compareTo(keys[i])==0)
return keys[i];
return keys[i-1];
}
public void delete(Key key)/*从表中删去键key（及其对应的值）*/
{
if(!contains(key))
return;
int i=rank(key);
for(int j=i;j+1<N;j++)
{
keys[j]=keys[j+1];
vals[j]=vals[j+1];
}
N--;
if(N>0&&N==keys.length/4)
resize(keys.length/2);
}
public void resize(int max)                /*动态调整数组大小*/
{
Key[] kt=(Key[])new Comparable[max];
Value[] vt=(Value[])new Comparable[max];
for(int i=0;i<N;i++)
{
kt[i]=keys[i];
vt[i]=vals[i];
}
keys=kt;
vals=vt;
}
public boolean contains(Key key)          /*键key是否存在于表中*/
{
int i=rank(key);
if(i<N&&keys[i].compareTo(key)==0)
return true;
return false;
}
public Iterable<Key> keys(Key lo,Key hi) /*[lo..hi]之间的所有键，已排列*/
{
Queue<Key> q=new Queue<Key>();
for(int i=rank(lo);i<rank(hi);i++)
q.enqueue(keys[i]);
if(contains(hi))
q.enqueue(keys[rank(hi)]);
return q;
}
}

在查找时，我们先将被查找的键和子数组的中间键比较。如果被查找的键小于中间键，我们就在左子数组中继续查找，如果大于我们就在右子数组中继续查找，否则中间键就是我们要找的键。

                          

 

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,mid+1,hi);
else if(cmp<0)
return rank(key,lo,mid-1);
else return mid;
}

                                                                     

package _3_Searching;

import java.util.Scanner;

/** 符号表的用例-计频器
 * 从输入中得到一列字符串并记录每个字符串的出现次数，然后遍历所有键并找出出现频率最高的键
*/
public class FrequencyCounter
{

public static void main(String[] args)
{
int minLen=2;            /*最小键长*/
Scanner sc=new Scanner(System.in);
BinarySearchST<String,Integer> st=new BinarySearchST<String,Integer>(5);
//SequentialSearchST<String,Integer>  st=new SequentialSearchST<String,Integer> ();
while(true)
{
String s=sc.nextLine();
if(s.equals("eof"))
break;
if(s.length()<minLen) /*忽略较短的单词*/
continue;
if(!st.contains(s))
st.put(s,1);
else 
st.put(s, st.get(s)+1);
}
String max=" ";
st.put(max, 0);
for(String i:st.keys(st.min(),st.max()))
if(st.get(i)>st.get(max))
max=i;
System.out.println(max+" "+st.get(max));
}

}