本文主要是介绍4大查找算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.背景

查找算法经常被面试问到...

2.代码

2.1.线性查找算法

package com.ldp.structure.demo03Search;

import org.junit.Test;

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

/**
 * @create 04/17 12:03
 * @description <p>
 * 线性查找
 * </p>
 */
public class Test01LinearSearch {
    /**
     * 测试线性查找
     */
    @Test
    public void test01() {
        int[] array = {14, 57, 2, 1, 96, 74, 9, 2, 708};
        List<Integer> integers = linearSearch(array, 2);
        System.out.println(integers);
    }

    /**
     * 线性查找
     *
     * @param array
     * @param searchValue
     * @return
     */
    public List<Integer> linearSearch(int[] array, int searchValue) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (searchValue == array[i]) {
                list.add(i);
            }
        }
        return list;
    }
}

2.2.二分查找算法

package com.ldp.structure.demo03Search;

import org.junit.Test;

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

/**
 * @create 04/17 12:09
 * @description <P>
 * 二分查找
 * </P>
 */
public class Test02TwoBranchSearch {
    @Test
    public void test01() {
        int[] array = {1, 2, 3, 4, 5};
        int searchSingle = twoBranchSearchSingle(array, 0, array.length - 1, -4);
        System.out.println(searchSingle);
    }

    @Test
    public void test02() {
        int[] array = {1, 2, 2, 3, 4, 5, 6, 7, 8};
        List<Integer> searchMore = twoBranchSearchMore(array, 0, array.length - 1, 2);
        System.out.println("-2=" + searchMore);
    }

    /**
     * 前提改数组是一个有序数组
     * 二分查找-查询单个
     *
     * @param array
     * @param left
     * @param right
     * @param searchValue
     * @return
     */
    public int twoBranchSearchSingle(int[] array, int left, int right, int searchValue) {
        if (left >= right) {
            return -1;
        }
        int middle = (left + right) / 2;
        if (searchValue < array[middle]) { // 左递归
            return twoBranchSearchSingle(array, left, middle, searchValue);
        } else if (searchValue > array[middle]) {// 右递归
            return twoBranchSearchSingle(array, middle + 1, right, searchValue);
        } else {
            return middle;
        }
    }

    /**
     * 前提改数组是一个有序数组
     * 二分查找-查询多个
     *
     * @param array
     * @param left
     * @param right
     * @param searchValue
     * @return
     */
    public List<Integer> twoBranchSearchMore(int[] array, int left, int right, int searchValue) {
        if (left >= right) {
            // 没有找到的情况
            return new ArrayList<>();
        }
        int middle = (left + right) / 2;
        if (searchValue < array[middle]) { // 左递归
            return twoBranchSearchMore(array, left, middle, searchValue);
        } else if (searchValue > array[middle]) {// 右递归
            return twoBranchSearchMore(array, middle + 1, right, searchValue);
        } else {
            // 因为数组是有序的,因此如果查找到了的话,可能左边,右边都有相同的值,如: [1,2,2,3,4,5,6,7,8]
            List<Integer> result = new ArrayList<>();
            result.add(middle);
            // 向左查找满足条件的值
            for (int i = (middle - 1); i >= left; i--) {
                if (array[i] == searchValue) {
                    result.add(i);
                } else {
                    break;
                }
            }
            // 向右查找满足条件的值
            for (int i = (middle + 1); i <= right; i++) {
                if (array[i] == searchValue) {
                    result.add(i);
                } else {
                    break;
                }
            }
            return result;
        }
    }
}

2.3.插值查找算法

package com.ldp.structure.demo03Search;

import org.junit.Test;

/**
 * @create 04/17 12:09
 * @description <P>
 * 插值查找-算法(数组必须有序)
 * </P>
 */
public class Test03InsertValueSearch {
    // 统计分解次数
    int count = 0;

    @Test
    public void test01() {
        int[] array = {1, 2, 2, 3, 4, 5, 6, 7, 8};
        Integer numIndex = insertValueSearchSingle(array, 0, array.length - 1, 8);
        System.out.println("分解次数:" + count + ",下标为:" + numIndex);
    }

    /**
     * 前提改数组是一个有序数组
     * 二分查找-查询单个
     *
     * @param array
     * @param left
     * @param right
     * @param searchValue
     * @return
     */
    public int insertValueSearchSingle(int[] array, int left, int right, int searchValue) {
        // 统计分解次数
        count++;
        // array[left] > searchValue 或者 array[right] < searchValue,查找的值不在序列范围内
        if (left >= right || array[left] > searchValue || array[right] < searchValue) {
            return -1;
        }
        // int middle = (left + right) / 2; // 二分查找算法公式
        int middle = left + (right - left) * (searchValue - array[left]) / (array[right] - array[left]);
        if (searchValue < array[middle]) { // 左递归
            return insertValueSearchSingle(array, left, middle, searchValue);
        } else if (searchValue > array[middle]) {// 右递归
            return insertValueSearchSingle(array, middle + 1, right, searchValue);
        } else {
            return middle;
        }
    }
}

2.4.斐波那契(黄金分割)查找算法

package com.ldp.structure.demo03Search;

import org.junit.Test;

import java.util.Arrays;

/**
 * @create 04/17 12:09
 * @description <P>
 * 斐波那契(黄金分割)查找-算法(数组必须有序)
 * </P>
 */
public class Test04GoldenSearch {
    // 统计分解次数
    @Test
    public void test01() {
        int[] array = {1, 2, 2, 3, 4, 5, 6, 7, 8};
        Integer numIndex = goldenSearchSingle(array, 4);
        System.out.println("下标为:" + numIndex);
    }

    /**
     * 斐波那契(黄金分割)查找-算法(数组必须有序)
     *
     * @param array
     * @param searchValue
     * @return
     */
    public int goldenSearchSingle(int[] array, int searchValue) {
        // 左侧
        int left = 0;
        int right = array.length - 1;
        // 不在查找范围内
        if (searchValue < array[left] || searchValue > array[right]) {
            return -1;
        }
        // 斐波那契数组
        int[] fbArray = fb();
        // k为斐波那契数组的下标,这里默认0
        int k = 0;
        // 寻找一个合适的k
        while (right > fbArray[k] - 1) {
            k++;
        }
        // 如果 fbArray[k]> right,补充新的数组
        int[] tempArray = Arrays.copyOf(array, fbArray[k]);
        // 使用原来数组的最后一个值填充,新数组中为空的值,
        // 比如原数组为array=[1,2,3,4,5],tempArray=[1,2,3,4,5,无值,无值],填充后tempArray=[1,2,3,4,5,5,5],即使用最后一个值填充
        for (int i = right; i < fbArray[k]; i++) {
            tempArray[i] = array[right];
        }
        while (left <= right) {
            int middle = left + fbArray[k] - 1; // 斐波那契公式
            if (searchValue < tempArray[middle]) {
                // 在左侧找
                right = middle - 1;
                k--;
            } else if (searchValue > tempArray[middle]) {
                // 在右侧找
                left = middle + 1;
                k = k - 2;  // 公式 f(k)=f(k-1)+f(k-2)==> 右拆分相当于对 f(k-2),继续拆分f(k-2)=f(k-3)+f(k-4),因此k=k-2
            } else {
                // 确定返回下标
                if (middle > right) {
                    return right;
                } else {
                    return middle;
                }
            }
        }
        return -1;
    }

    /**
     * 获取一个斐波那契数组
     *
     * @return
     */
    public int[] fb() {
        int[] fbArray = new int[20];
        fbArray[0] = 1;
        fbArray[1] = 1;
        for (int i = 2; i < 20; i++) {
            fbArray[i] = fbArray[i - 1] + fbArray[i - 2];
        }
        return fbArray;
    }
}

完美

这篇关于4大查找算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！