2022-02-21 八、查找(上:线性、二分)

查找(上:线性、二分)

1. 线性查找

1.1 基本介绍

一种简单的查找方式,从头到尾遍历,直到找到指定数字。

1.2 设计思路

for/while循环遍历数组,找到指定数字则返回下标,否则返回-1。

1.3 代码实现

public class Demo24 {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 1000, 1234};

        int num = 81;
        if (seqSearch(arr, num) == -1) {
            System.out.println("未找到");
        } else {
            System.out.println(seqSearch(arr, num));
        }
    }

    /**
     * 线性查找
     * @param arr 数组
     * @param value 目标值
     * @return 下标
     */
    public static int seqSearch(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) {
                return i;
            }
        }
        return -1;
    }
}

2. 二分查找

2.1 基本介绍

二分查找又称折半查找,即从中间数开始找,然后根据比较结果选择需要折半的一边出发,然后再次折半,以此类推找出元素。
注意:二分法需要数据首先有序

2.2 设计思路-单数版

  1. 确定当前数组的下标 mid = (left + right)/2;
  2. 让需要查找的数 findVal 和 arr[mid] 比较
    (1) findVal > arr[mid] 说明要查找的数在 mid 右边,因此向右递归查找
    (2) findVal < arr[mid] 说明要查找的数在 mid 左边,因此向左递归查找
    (3) findVal = arr[mid] 说明找到,返回下标

2.3 代码实现

public class Demo25 {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 99, 100, 111, 112, 113, 115, 1000,
                1000, 1000, 1000, 1000, 1234};
                
        ArrayList<Integer> findIndex = new ArrayList<>();
        int findVal = 0;
        System.out.println(binarySearch(arr, 0, arr.length - 1, findVal));
    }

    /**
     * 单个数据查找
     * @param arr 数组
     * @param left 左下标
     * @param right 右下标
     * @param findVal 目标值
     * @return 下标
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        // 判断递归结束的临界条件
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        // 取中间值
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal == midVal) {
            return mid;
        }
        return findVal > midVal ? binarySearch(arr, mid + 1, right, findVal)
                : binarySearch(arr, left, mid - 1, findVal);

    }
}

可以发现,上述代码只能寻找到单个符合条件的目标值,局限性大,因此对代码做个调整

2.4 设计思路

  1. 找到第一个匹配的索引值mid的时候,不要马上返回;
  2. mid索引值的左边扫描,将所有与findVal相等的元素的下标加入到返回集合中;
  3. mid索引值的右边扫描,将所有与findVal相等的元素的下标加入到返回集合中;
  4. 整体返回。

2.5 代码实现

public class Demo25 {
    public static void main(String[] args) {
        int[] arr = {1, 8, 10, 89, 99, 100, 111, 112, 113, 115, 1000,
                1000, 1000, 1000, 1000, 1234};
                
        ArrayList<Integer> findIndex = new ArrayList<>();
        int findVal = 0;
        System.out.println(binarySearch2(arr, 0, arr.length - 1, findVal));
        System.out.println(binarySearch3(findIndex, arr, 0, arr.length - 1, findVal));
    }

    /**
     * 找所有符合的目标值下标
     * @param arr 数组
     * @param left 左下标
     * @param right 右下标
     * @param findVal 目标值
     * @return 目标值下标集合
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        // 当 left > right 时候,说明已经递归完毕,仍没有找到
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return new ArrayList<>();
        }
        // 折半,取值
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal == midVal) {
            final ArrayList<Integer> list = new ArrayList<>();
            list.add(mid);
            int index = mid - 1;
            // 向左找,注意临界条件
            while (index >= 0 && arr[index] == midVal) {
                list.add(index--);
            }
            index = mid + 1;
            // 向右找
            while (index <= right && arr[index] == midVal) {
                list.add(index++);
            }
            return list;
        }
        return findVal > midVal ? binarySearch2(arr, mid + 1, right, findVal)
                : binarySearch2(arr, left, mid - 1, findVal);

    }

    /**
     * 递归法
     */
    public static List<Integer> binarySearch3(List<Integer> findIndex, int[] arr, int left, int right, int findVal) {
        // 当 left > right 时候,说明已经递归完毕,仍没有找到
        if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return new ArrayList<>();
        }
        // 折半,取值
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal == midVal) {
            findIndex.add(mid);
            binarySearch3(findIndex, arr, left, mid - 1, findVal);
            binarySearch3(findIndex, arr, mid + 1, right, findVal);
            return findIndex;
        }
        return findVal > midVal ? binarySearch3(findIndex, arr, mid + 1, right, findVal)
                : binarySearch3(findIndex, arr, left, mid - 1, findVal);

    }
}

上一篇 总目录 下一篇
七、排序(下:归并、基数) 数据结构篇(Java)目录 未完待续
上一篇:OpenCV成长之路(9):特征点检测与图像匹配


下一篇:Java并发案例05---Master-Worker模式