目录

1.二分法查找

 2.插值查找

 3斐波那契查找

1.二分法查找

二分法查找（折半查找）：

第一：二分法查找建立在排序的基础之上。

第二：二分法查找效率要高于“一个挨着一个”的这种查找方式。

第三：二分法查找原理？

10(0下标) 23 56 89 100 111 222 235 500 600(下标9) arr数组

目标：找出600的下标

(0 + 9) / 2 --> 4（中间元素的下标）

arr[4]这个元素就是中间元素：arr[4]是 100

100 < 600

说明被查找的元素在100的右边。

那么此时开始下标变成：4 + 1

(5 + 9) / 2 --> 7（中间元素的下标）

arr[7] 对应的是：235

235 < 600

说明被查找的元素在235的右边。

开始下标又进行了转变：7 + 1

(8 + 9) / 2 --> 8

arr[8] --> 500

500 < 600

开始元素的下标又发生了变化：8 + 1

(9 + 9) / 2 --> 9

arr[9]是600，正好和600相等，此时找到了。

public class BinarySearch {

    public static void main(String[] args) {

        int[] array = new int[]{10,11,12,13,14,15,16,17};

        int target = 10;

        int index = search(array, target);
        System.out.println(index);


    }
    public static int search(int[] array,int target){
        //最小索引指针
        int min = 0;

        int max = array.length-1;

        while (min<=max){
            //算出平均索引位置
            int mid = (min+max)/2;
            if (array[mid]== target){
                return mid;
            }

            if (array[mid]target){
                max = mid-1;
            }

        }

        return -1;
    }

}

 2.插值查找

 数组 arr = [1, 2, 3, ......., 100]

假如我们需要查找的值 1

使用二分查找的话，我们需要多次递归，才能找到 1

使用插值查找算法

int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

int mid = 0 + (99 - 0) * (1 - 1)/ (100 - 1) = 0 + 99 * 0 / 99 = 0

比如我们查找的值 100

int mid = 0 + (99 - 0) * (100 - 1) / (100 - 1) = 0 + 99 * 99 / 99 = 0 + 99 = 99

package com.bjpowernode.select;


public class InsertSelect {

    public static void main(String[] args) {

        int[] array = {1,2,3,4,5,6};

        int left = 0;
        int right = array.length-1;

        int searchVal = 1;

        System.out.println(select(array,left,right,searchVal));

    }

    public static int select(int[] array,int left,int right,int searchVal){

        
        if (left>right || searchValarray[array.length-1]){
            return -1;
        }

        int mid = left+(right-left)*(searchVal-array[left])/(array[right]-array[left]);
        int midValue = array[mid];
        if (searchVal>midValue){
            return select(array,mid+1,right,searchVal);
        }else if (searchVal 
 3斐波那契查找 
 
 
 
 斐波那契不再是中间，而是位于黄金分割点附近，即  mid=low+F(k-1)-1
 
 
由斐波那契数列F[k]=F(k-1)+F(k-2)的性质，可以得到 (F[k]-1) = (F(k-1) -1) +(F[k-2]-1) +1 . 
 
 
对F(k-1)-1的理解:
 
 
1) 只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,从而中间位置为mid=low+F(k-1)-1。
 
 
2)类似的，每一字段也可以用相同的方式分割
 
 
3）但顺序表长度n不一定刚好等于F[K]-1，所以需要将原来的顺序表长度n增加至F[K]-1。这里的k值只要能使得F[K]-1恰好大于 或等于n即可，由以下代码得到,顺序表长度增加后，新增的位置（从n+1到F[k]-1位置）.都为n信置的值即可。
 
 
package com.bjpowernode.select;

import java.util.Arrays;


public class FibonacciSelect {


    public static void main(String[] args) {

        int[] array = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};

        System.out.println(select(array,13));
    }


    
    public static int[] f(){

        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2;if[k]-1){
            k++;
        }

        int[] temp = Arrays.copyOf(array,f[k]);

        
        for (int i = hight+1;itemp[mid]){
                low = mid+1;
                k-=2;

            }else{
                if (mid<=hight){
                    return mid;
                }else {
                    return hight;
                }

            }


        }

        return -1;
    }

}