三大查找算法

针对无序数列（数组）

	//顺序查找
	public static int sequenceSearch(int []arr,int key) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == key) {
				return i;
			}
		}
		return -1;
	}

针对有序序列（数组），主要有二分查找，插值查找，斐波拉契查找

	//二分（拆半）查找,针对有序数组
	public static int binarySearch(int[] arr,int key) {
		int low,high,mid;
		low = 0;
		high = arr.length-1;
		while (low <= high) {
			mid = (low + high)/2;
			if (key < arr[mid]) {
				high = mid - 1;
			}else if (key > arr[mid]) {
				low = mid + 1;
			}else {
				return mid;
			}
		}
		return -1;
	}
	
	//插值查找,针对有序数组
	public static int insertSearch(int[] arr,int key) {
		int low,high,mid;
		low = 0;
		high = arr.length-1;
		while (low <= high) {
			mid = low + (low + high) * (key - arr[low])/(arr[high] - arr[low]);
			if (key < arr[mid]) {
				high = mid - 1;
			}else if (key > arr[mid]) {
				low = mid + 1;
			}else {
				return mid;
			}
		}
		return -1;
	}
	
	//斐波拉契数列,针对有序数组
	//先定义一个斐波拉契数列
	public static int [] fib() {
		int []f =new int[20];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < f.length; i++) {
			f[i] = f[i-1] + f[i-2];
		}
		return f;
	}
	public static int fibsearch(int[] arr,int key) {
		int low=0;
		int high = arr.length;
		int mid;
		int k=0;
		int[] f= fib();
		while (high - 1 > f[k] - 1) {
			k++;
		}
		int []temp = Arrays.copyOf(arr, f[k] - 1);
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = temp[high];
		}
		while (low <= high) {
			mid = low + f[k-1] - 1;
			if (key < arr[mid]) {
				high = mid - 1;
				k--;
			}else if (key > arr[mid]) {
				low = mid + 1;
				k-=2;
			}else {
				if (mid <= high) {
					return mid;
				}else {
					return mid;
				}
			}
		}
		return -1;
	}