算法--java实现查找算法

1、二分查找

package use5;
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){
                min = mid+1;
            }
            if (array[mid]>target){
                max = mid-1;
            }
        }
        return -1;
    }
}

2、线性查找

package use5;

public class LinearSelect {

    public static void main(String[] args) {


        /**
         * 查询该数组下是否存在9这个元素，如果存在则返回索引值，否则返回-1
         */
        int[] array = new int[]{2,4,8,6,4,9,0};
        int i = show(array, 10);
        System.out.println(i);
    }
    public static int show(int[] array,int target){
        for (int i=0;i<array.length;i++){
            if (array[i]==target){
                return i;
            }
        }
        return -1;
    }
}

3、插值查找

package use5;
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 || searchVal<array[0] || searchVal>array[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<midValue){
            return select(array,left,mid-1,searchVal);
        }else {
            return mid;
        }
    }
}

4、斐波那契查找

package use5;
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));
    }
    /**
     * f[k] = (f[k-1])+ (f[k-2])
     * @return
     */
    public static int[] f(){
        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;
    }
    /**
     * mid = low+F(k-1)-1
     * @param array
     * @param key
     * @return
     */
    public static int select(int[] array,int key){
        int low = 0;
        int hight  = array.length-1;
        int k = 0;
        int mid = 0;
        int[] f = f();
        /**
         * 找分割点
         */
        while (hight>f[k]-1){
            k++;
        }
        int[] temp = Arrays.copyOf(array,f[k]);
        /**
         * {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}  -=》{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89，89,89,}
         */
        for (int i = hight+1;i<temp.length;i++){
            temp[i] = array[hight];
        }
        while (low<=hight){
            mid = low+f[k-1]-1;
            // f[k-1]+f[k-2] = f[k];
            if (key<temp[mid]){
                hight=mid-1;
                k--;
            }else if (key>temp[mid]){
                low = mid+1;
                k-=2;
            }else{
                if (mid<=hight){
                    return mid;
                }else {
                    return hight;
                }
            }
        }
        return -1;
    }
}