二分查找(Java)

二分查找(Java)

1.概念

二分查找（Binary Search）也叫作折半查找。二分查找有两个要求，一个是数列有序，另一个是数列使用顺序存储结构（比如数组）

2.思路分析

1.首先确定数组的中间下标：mid=（left+right）/2

2.然后让需要查找的数findVal和arr[mid]比较

​ 2.1 findVal > arr[mid] 说明要查找的数在 mid 右边，因此向右递归查找

​ 2.2 findVal < arr[mid] 说明要查找的数在 mid 左边，因此向左递归查找

​ 2.3 findVal = arr[mid] 说明找到，既返回

3.何时结束递归？

​ 3.1 找到就结束递归

​ 3.2 递归完整个数组仍然没找到findVal，也需要结束递归（left>right就需要结束）

3.代码

package DataStructuresAlgorithm.Search;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1234};
        int resIndex = binarySearch(arr, 0, arr.length - 1, 88);
        System.out.println(resIndex);
    }

    /**
     * @param arr     数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 需要查找的值
     * @author ZJ
     * Description 二分查找
     * date 2022-05-13 10:14:59 10:14
     */
    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        //当left>right，说明递归了整个数组，没找到
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }
}

但是，如果一个数组中有很多个相同的数，比如上面的数组有4个1000，查找后只会返回第一个1000的下标，代码还可以改进

1.找到第一个匹配的索引值 mid 的时候，不要马上返回

2.向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList

3.向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList

/**
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @author ZJ
     * Description 二分查找（查找值有多个的话，返回一个List）
     * date 2022-05-13 10:36:28 10:36
     */
    public static ArrayList<Integer> binarySearchMore(int[] arr, int left, int right, int findVal) {
        //当left>right，说明递归了整个数组，没找到
        if (left > right) {
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        ArrayList<Integer> resIndexList = new ArrayList<>();

        if (findVal > midVal) {//向右递归
            return binarySearchMore(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return binarySearchMore(arr, left, mid - 1, findVal);
        } else {
            //向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || findVal != arr[temp]) {
                    break;
                }
                //否则，就把temp放到ArrayList中
                resIndexList.add(temp);
                temp -= 1;//temp左移
            }
            resIndexList.add(mid);

            //向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || findVal != arr[temp]) {
                    break;
                }
                //否则，就把temp放到ArrayList中
                resIndexList.add(temp);
                temp += 1;//temp右移
            }
        }
        return resIndexList;
    }

完整代码

package DataStructuresAlgorithm.Search;

import java.util.ArrayList;

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1000, 1000, 1000, 1234};
//        int resIndex = binarySearchOne(arr, 0, arr.length - 1, 88);
//        System.out.println(resIndex);
        ArrayList<Integer> reIndexList = binarySearchMore(arr, 0, arr.length - 1, 1000);
        System.out.println(reIndexList);
    }

    /**
     * @param arr     数组
     * @param left    左边的索引
     * @param right   右边的索引
     * @param findVal 需要查找的值
     * @author ZJ
     * Description 二分查找（只返回一个）
     * date 2022-05-13 10:14:59 10:14
     */
    public static int binarySearchOne(int[] arr, int left, int right, int findVal) {
        //当left>right，说明递归了整个数组，没找到
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];
        if (findVal > midVal) {//向右递归
            return binarySearchOne(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return binarySearchOne(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

    /**
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @author ZJ
     * Description 二分查找（查找值有多个的话，返回一个List）
     * date 2022-05-13 10:36:28 10:36
     */
    public static ArrayList<Integer> binarySearchMore(int[] arr, int left, int right, int findVal) {
        //当left>right，说明递归了整个数组，没找到
        if (left > right) {
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;
        int midVal = arr[mid];

        ArrayList<Integer> resIndexList = new ArrayList<>();

        if (findVal > midVal) {//向右递归
            return binarySearchMore(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            return binarySearchMore(arr, left, mid - 1, findVal);
        } else {
            //向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || findVal != arr[temp]) {
                    break;
                }
                //否则，就把temp放到ArrayList中
                resIndexList.add(temp);
                temp -= 1;//temp左移
            }
            resIndexList.add(mid);

            //向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回，加入到ArrayList
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || findVal != arr[temp]) {
                    break;
                }
                //否则，就把temp放到ArrayList中
                resIndexList.add(temp);
                temp += 1;//temp右移
            }
        }
        return resIndexList;
    }
}