数据结构与算法——查找算法-二分查找

2021-12-12 01:25:01

简单介绍

二分查找 也称 折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列，说简单点就是要求查找的数组是有序的。

思路分析

搜索过程从数组（有序的）的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
如果要查找元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

看动图体验一下，下面的动图是二分查找与顺序查找的对比：

上面的思路如果看不懂，下面举个例子并代码实现。

请对一个 有序数组 进行二分查找 {1,8, 10, 89, 1000, 1234}，输入一个数查找该数组是否存在此数，并且输出下标，如果没有就提示「没有这个数」。

二分查找可以使用递归和 非递归 实现，这里使用递归方式实现。

查找步骤：

首先确定该数组的中间下标
```
int  mid = (left + right)/2
```
然后让需要查找的数 findVal和 arr[mid] 比较
1. findVal > arr[i]，说明要查找的数在数组右边
2. findVal < arr[i] ，说明要查找的数在数组左边
3. findVal == arr[i]，说明已经找到，就返回

什么时候结束递归呢？

找到则结束递归

未找到，则结束递归

当 left > right 时，表示整个数组已经递归完，说明没有找到，结束递归。这里要动脑筋思考一下，它往左或往右查找却没有找到目标数， left 和right的情况，脑子里走一遍过程。

{1,8, 10, 89, 1000, 1234} 共 5 个
查找 -1
第一轮：
	int mid = (0 + 5)/2 = 2
	arr[mid] = 10
   -1 < 10,往左边查找
第二轮：下面为什么是 - 1，而不是 - 2或其他的呢，是因为 arr[mid] 如果等于要查找的数就返回了，已经判断过了，不需要再判断
	mid = (0 + 1)/2 = 0
	arr[mid] = 10
   -1 < 1,往左边
第三轮：同理，这时 left = 0，right = -1
   left 就大于 right 了

代码实现

/**
 * 二分查找
 */
public class BinarySearchTest {
    @Test
    public void binaryTest() {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1234};
        int findVal = 89;
        int result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = -1;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 123456;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));

        findVal = 1;
        result = binary(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == -1 ? "未找到" : "找到值，索引为：" + result));
    }

    /**
     * @param arr
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 未找到返回 -1，否则返回该值的索引
     */
    private int binary(int[] arr, int left, int right, int findVal) {
        // 当找不到时，则返回 -1
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;//数组中间值的下标
        int midVal = arr[mid];//数组中间值
        // 相等则找到
        if (midVal == findVal) {
            return mid;
        }
        // 判断值是否在右边，如果要查找的值在右边，则右递归
        if (findVal > midVal) {
            // mid 的值，就是当前对比的值，所以不需要判定
            return binary(arr, mid + 1, right, findVal);//动脑筋
        }
        //否则向左查找，左递归
        return binary(arr, left, mid - 1, findVal);
    }
}

测试输出

查找值 89：找到值，索引为：3
查找值 -1：未找到
查找值 123456：未找到
查找值 1：找到值，索引为：0

可以看到，这个算法已经实现了，但是还有一个问题，仔细观察，你就会发现上面的代码实现的算法有个缺点，那就是如果数组中要查找的数存在多个，那么它只能返回第一个查找到的数的下标。

下面我们就来优化这个缺点。

查找出所有符合要求的值

请对一个 有序数组 进行二分查找 {1,8, 10, 89, 1000, 1000,1234}，输入一个数查找该数组是否存在此数，并且求出所有下标，如果没有就提示「没有这个数」。

增加难度：返回该值所有下标

  @Test
    public void binary2Test() {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1234};
        int findVal = 89;
        List<Integer> result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = -1;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 123456;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 1;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));

        findVal = 1000;
        result = binary2(arr, 0, arr.length - 1, findVal);
        System.out.println("查找值 " + findVal + "：" + (result == null ? "未找到" : "找到值，索引为：" + result));
    }

    /**
     * 查找所有符合条件的下标
     *
     * @param arr
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 要查找的值
     * @return 未找到返回 null，否则返回该值的索引集合
     */
    private List<Integer> binary2(int[] arr, int left, int right, int findVal) {
        // 当找不到时，则返回 null
        if (left > right) {
            return null;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        // 相等则找到
        if (midVal == findVal) {
            //定义一个集合，保存满足要求的数的下标
            List<Integer> result = new ArrayList<>();
            // 如果已经找到，则先不要退出
            // 因为二分查找的前提是：对一个有序的数组进行查找
            // 所以，我们只需要，继续挨个的往左边和右边查找目标值就好了
            int tempIndex = mid - 1;//这里是第一个满足条件的数的下标的左边一个数的下标
            result.add(mid); //先把当前找到的下标添加进集合
            // 先往左边找
            while (true) {
                // 当左边的数组已经找完
                // 或 找到一个不与目标值相等的值，就可以跳出左边查找。 这里动一下脑筋
                if (tempIndex < 0 || arr[tempIndex] != midVal) {
                    break;
                }
                result.add(tempIndex);
                tempIndex--;//找到了，继续往左一个
            }
            // 再往右边查找
            tempIndex = mid + 1;//这里是第一个满足条件的数的下标的右边一个数的下标
            while (true) {
                // 这里也跟上面一样，当右边的数组已经找完
                // 或 找到一个不与目标值相等的值，就可以跳出右边查找。 这里动一下脑筋
                if (tempIndex >= arr.length || arr[tempIndex] != midVal) {
                    break;
                }
                result.add(tempIndex);
                tempIndex++;//找到了，继续往右一个
            }
            //找完了返回下标集合
            return result;
        }
        // 判断值是否在右边，如果要查找的值在右边，则右递归
        if (findVal > midVal) {
            // mid 的值，就是当前对比的值，所以不需要判定
            return binary2(arr, mid + 1, right, findVal);
        }
        //否则向左查找，左递归
        return binary2(arr, left, mid - 1, findVal);
    }

测试输出信息

查找值 89：找到值，索引为：[3]
查找值 -1：未找到
查找值 123456：未找到
查找值 1：找到值，索引为：[0]
查找值 1000：找到值，索引为：[5, 4]

tip：这个算法很简单，但是很实用。必须要掌握。

数据结构与算法——查找算法-二分查找

码农公寓

简单介绍

思路分析

代码实现

查找出所有符合要求的值

相关文章