算法(第四版)学习笔记之二分查寻的递归与非递归java实现

算法(第四版)学习笔记之二分查找的递归与非递归java实现

二分查找是基于有序数组的，在查找时，我们先将被查找的键和子数组的中间键比较。如果被查找的键小于中间键，我们就在左子数组中继续查找；如果被查找的键大于中间键，我们就在右子数组中继续查找。在下面的代码中，将使用二分查找来获取元素和添加新元素同时插入在正确的位置中，代码如下：

/**
 * 
 * @author seabear
 * 二分查找：递归及非递归
 * @param <Key>
 * @param <Value>
 */

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;
	}
	
	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 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;
		}
		for(int j = N; j > i; j--)
		{
			keys[j] = keys[j-1];
			values[j] = values[j-1];
		}
		keys[i] = key;
		values[i] = value;
		N++;
	}
	

	
	//非递归
	public int rank(Key key)
	{
		int lo = 0;
		int hi = N - 1;
		while(lo <= hi)
		{
			int mid = lo + (hi - lo) / 2;
			int com = key.compareTo(keys[mid]);
			if(com < 0)
			{
				hi = mid - 1;
			}
			else if(com > 0)
			{
				lo = mid + 1;
			}
			else
			{
				return mid;
			}
		}
		return lo;
	}
	
	//递归
	public int rank(Key key,int lo,int hi)
	{
		if(hi < lo)
		{
			return lo;
		}
		int mid = lo + (hi - lo) / 2;
		int com = key.compareTo(keys[mid]);
		if(com < 0)
		{
			return rank(key,lo,mid-1);
		}
		else if(com > 0)
		{
			return rank(key,mid + 1,hi);
		}
		else
		{
			return mid;
		}
	}
	

}