查找算法

查找算法介绍

在java中，我们常用的查找有四种

1) 顺序(线性查找)
2) 二分查找/折半查找
3) 插值查找
4) 斐波那契查找

线性查找

二分查找

思路图解

代码实现

import java.util.ArrayList;
import java.util.List;

public class BinarySearch {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int arr[]= {1,8,10,89,1000,1000,1000,1234};
        //System.out.println(binarySearch(arr,0,arr.length-1,89));
        System.out.println(binarySearch2(arr,0,arr.length-1,1000));
    }

    public static int binarySearch(int[] arr,int left,int right,int findValue){

        if(left>right) {       //说明没有找到
            return -1;      
        }
        int mid=(left+right)/2;
        int midVal=arr[mid];

        if(midVal>findValue) {
            return binarySearch(arr,left,mid-1,findValue);
        }else if(midVal<findValue) {
            return binarySearch(arr,mid+1,right,findValue);
        }else {
            return mid;
        }
    }

    //binarySort只使用不存在相同元素的数组，如果问想要找出某数值对应的所有下标，
        //并存放在list中，编写binarySort2方法
    public static List<Integer> binarySearch2(int[] arr,int left,int right,int findValue){

        if(left>right) {       //说明没有找到
            return new ArrayList<Integer>();      
        }
        int mid=(left+right)/2;
        int midVal=arr[mid];

        if(midVal>findValue) {
            return binarySearch2(arr,left,mid-1,findValue);
        }else if(midVal<findValue) {
            return binarySearch2(arr,mid+1,right,findValue);
        }else {
            List<Integer> resIndexlist=new ArrayList<Integer>();
            int temp=mid-1;
            while(arr[temp]==findValue) {
                resIndexlist.add(temp);
                temp--;
            }
            resIndexlist.add(mid);
            temp=mid+1;
            while(arr[temp]==findValue) {
                resIndexlist.add(temp);
                temp++;
            }
            return resIndexlist;
        }
    }
}

插值查找

插值查找原理
①插值查找算法类似于二分查找，不同的是插值查找每次自适应mid处开始查找。
②将二分查找中的求mid公式替换如下：
mid=left+(right-left)*(findValue-arr[left])/(arr[right]-arr[left])

利用案例进行图解

注意事项
①对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快。
②关键字分布不均匀的情况下，该方法不一定比二分查找好

代码实现

public class InsertValueSearch {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] arr= new int[100];
        for(int i=0;i<100;i++) {
            arr[i]=i+1;
        }
        System.out.println(insertValueSearch(arr,0,arr.length-1,100));
    }

    public static int insertValueSearch(int[] arr,int left,int right,int findValue){

        //说明没有找到
        //注意findValue<arr[0]与findValue>arr[arr.length-1]必须需要，否则可能会越界
        if(left>right||findValue<arr[0]||findValue>arr[arr.length-1]) {       
            return -1;      
        }
        int mid=left+(right-left)*(findValue-arr[left])/(right-left);
        int midVal=arr[mid];

        if(midVal>findValue) {
            return insertValueSearch(arr,left,mid-1,findValue);
        }else if(midVal<findValue) {
            return insertValueSearch(arr,mid+1,right,findValue);
        }else {
            return mid;
        }
    }
}

插值查找整体思路与二分插值相似，主要在对mid的更新上不同，以及对查找不出findValue的判定上。

斐波那契查找