java实现有序查找：折半查找、插值插值、斐波那契查找

今天动手实现了折半查找、插值查找以及斐波那契查找，其中斐波那契查找比较难，需要好好理解。如有错误，欢迎探讨。Talk is cheap,show me the code.

package com.chenli.Find;

import java.util.Arrays;

/**
 * 有序查找：
 * 1、折半查找
 * 2、插值查找
 * 3、斐波那契查找
 * @author 陈力
 *
 */
public class Find {

	public static void main(String[] args) {
		int []array = {1,3,5,12,15,18,21,34,38,41,43,47};
		
		int index1 = bisearch(array, 34);//折半查找
		System.out.println(index1);
		
		int index2 = Interplation_Search(array, 21);//插值查找	
		System.out.println(index2);
		
		//斐波那契查找
		int index3 = Fibonacci_Search(array, 47);
		System.out.println(index3);

	}
	
	/**
	 * 折半查找
	 * @param array 指定数组
	 * @param key 指定要查找的值
	 * @return 
	 * 时间复杂度为O(logn)
	 * 
	 */
	public static int bisearch(int []array,int key){
		
		int low = 0;
		int high = array.length-1;
		int mid ;
		
		while(low<=high){
			mid = (low+high)/2;//关键代码  也可以写成：mid = low + 1/2*(high-low)
			if(key<array[mid]){
				high = mid-1;
			}
			else if(key>array[mid]){
				low = mid+1;
			}
			else{
				return mid;
			}
		}
		
		return -1;
		
	}
	
	/**
	 * 插值查找:是关键字key和最大最小记录关键值比较后的查找方法
	 * 核心：(key-array[low])/(array[high]-array[low])
	 * 时间复杂度也是O(logn)
	 * 适用性：表长较长，关键字分布比较均匀的查找表。这种情况下，插值查找比折半查找平均性能好很多。但是这种就不适用了{0,1，998，999...}分布不均匀
	 * 
	 */
	public static int Interplation_Search(int[]array,int key){
		
		int low = 0;
		int high = array.length-1;
		int mid ;
		
		while(low<=high){
			mid = low + (key-array[low])/(array[high]-array[low])*(high-low);//关键代码
			if(key<array[mid]){
				high = mid-1;
			}
			else if(key>array[mid]){
				low = mid+1;
			}
			else{
				return mid;
			}
		}
		
		return -1;
		
	}
	
	/**
	 * 斐波那契查找：利用黄金分割原理实现
	 * 适用：题目要求仅使用加减法实现二分查找
	 * 要求：开始表中记录的个数（n）为某个斐波那契数小1，即n=F(k)-1;为什么？
	 * 是为了格式上的统一，以方便递归或者循环程序的编写。表中的数据是F(k)-1个，使用mid值进行分割用掉一个，
	 * 那么剩下F(k)-2个。正好分给两个子序列，每个子序列的个数分别是F(k-1)-1与F(k-2)-1个，格式上与之前F(k)-1是统一的。
	 * 
	 */
	private static int max_size = 20;
	
	//生成斐波那契数列
	public static int[]fibonacci(){
		int []F = new int[max_size];
		F[0] = 1;
		F[1] = 1;
		for(int i=2;i<max_size;i++){
			F[i] = F[i-1] + F[i-2];
		}
		return F;
	}
	
	public static int Fibonacci_Search(int[]array,int key){
		
		//获得斐波那契数列
		int[]F = fibonacci();
		
		int low = 0;
		int high = array.length-1;
		int mid;
		int k = 0;//斐波那契分割数值下标
		
		//获得high在斐波那契数列的位置
		while(high > F[k]-1){
			k++;
		}
		
		//构造新的数组取代原来的数组,长度为斐波那契F[k]的值
		int [] newArray = Arrays.copyOf(array,F[k]);
		
		//对新构造的数组进行值补充，使其都等于原数组最后一位的值。
		//为什么要等于原数组最后一位的值呢？
		//为了避免查找原数组最后一位而出现失败。
		for(int i=array.length;i<newArray.length;i++){
			newArray[i] = array[high];
		} 
		
		while(low<=high){
			mid = low + F[k]-1;
			if(key<newArray[mid]){
				high = mid - 1;
				k = k-1;//为什么k=k-1?看前面注释，理解开始表中记录的个数（n）为某个斐波那契数小1，即n=F(k)-1
			}
			else if(key>newArray[mid]){
				low = mid + 1;
				k = k-2;//为什么k=k-2?看前面注释，理解开始表中记录的个数（n）为某个斐波那契数小1，即n=F(k)-1
			}
			else{
				if(mid<=high){//若小于或相等，说明mid即为要查找的位置
					return mid;
				}else{//若mid>high，即mid为补全的值，补全的值即为查找原数组最后一位。
					return high;
				}
			}
		}
		return -1;	
	}	
}