首页  思维导图  详情

七大查找算法

2021-04-03 15:50:53   12  举报





AI智能生成

请大家不要直接克隆，着手梳理一遍才会变成自己的知识

查找算法

二分查找

斐波那契

作者其他创作

大纲/内容

顺序查找

实现方式

数组遍历

代码实现

/**
 * @author 小也
 * @create 2021/4/3 8:04
 */
public class SequentialSearch {
    public static void search(int[] arr,int x) {
        boolean has = false;
        for (int i : arr) {
            if(i == x){
                System.out.println("x存在");
                has = true;
                break;
            }
        }
        if (!has) {
            System.out.println("x不存在");
        }
    }
}

二分查询

前提

数组必须有序

实现方式

递归

代码实现

/**
 * @author 小也
 * @create 2021/4/3 8:09
 */
public class BinarySearch {
    public static void search(int[] arr,int left,int right,int x) {
        if (x < arr[left] || x > arr[right]){
            System.out.println("x不存在");
            return;
        }
        int mid = left + (right - left)/2;
        if (x == arr[mid]){
            System.out.println("x存在");
        }

        if (x < arr[mid]){
            search(arr,left,mid - 1,x);
        }
        if (x > arr[mid]){
            search(arr,mid + 1,right,x);
        }
    }
}

插值查找

是二分查找的改进

int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);

前提

数组必须有序

实现方式

递归

代码实现

/**
 * @author 小也
 * @create 2021/4/3 8:32
 */
public class InsertionSearch {
    public static void search(int[] arr,int left,int right,int x) {
        if (x < arr[left] || x > arr[right]){
            System.out.println("x不存在");
            return;
        }
        int mid = left + (x - arr[left])/(arr[right] - arr[left]) * (right - left);
        if (x == arr[mid]){
            System.out.println("x存在");
        }

        if (x < arr[mid]){
            search(arr,left,mid - 1,x);
        }
        if (x > arr[mid]){
            search(arr,mid + 1,right,x);
        }
    }
}

斐波那契查找

是二分查找的改进

mid = low + fib[k - 1] - 1;

前提

数组必须有序

实现方式

⭐非递归

代码实现

/**
 * @author 小也
 * @create 2021/4/3 9:10
 */
public class FibonacciSearch {
    /**
     * Fibonacci数组最大长度
     */
    private static final int MAX_LENGTH = 20;
    /**
     * 构造一个Fibonacci数组
     */
    private static int[] fib(){
        int[] fi = new int[MAX_LENGTH];
        fi[0] = 1;
        fi[1] = 1;
        for (int i = 2; i < fi.length; i++){
            fi[i] = fi[i - 1] + fi[i - 2];
        }
        return fi;
    }
    public static int search(int[] arr,int x) {
        int low = 0;
        int high = arr.length - 1;
        int mid = 0;
        int k = 0;
        int[] fib = fib();
        //找到略微大于等于x的那个分割点
        while (high > fib[k] - 1){
            k++;
        }
        //将数组扩容到F(k)-1
        int[] temp = new int[fib[k]-1];
        for(int i = 0; i < arr.length; i++){
            temp[i] = arr[i];
        }
        //超过arr数组长度的位置填充arr的最后一个元素
        for (int i = arr.length;i < fib[k]-1; i++){
            temp[i] = arr[high];
        }
        while(low <= high){
            mid = low + fib[k - 1] - 1;
            if (x < temp[mid]){
                high = mid - 1;
                k--;
            }else if(x > temp[mid]){
                low = mid + 1;
                k -= 2;
            }else{
                if (mid < high){
                    return mid;
                }else{
                    return high;
                }
            }
        }
        return -1;
    }
}