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

基本介绍

代码实现

    /**
     * 二分查找要求数组有序
     * @param arr 数组
     * @param left 左索引
     * @param right 右索引
     * @param value 查找的数据
     * @return 包含数据索引的集合
     */
    public static ArrayList<Integer> binarySearch(int[] arr, int left, int right, int value) {

        //没找到
        if (left > right) {
            return new ArrayList<Integer>();
        }

        int mid = (left + right) / 2;
        if (value > arr[mid]) { //向右递归
            return binarySearch(arr, mid + 1, right, value);
        } else if (value < arr[mid]) {   //向左递归
            return binarySearch(arr, left, mid - 1, value);
        } else {	//已找到，将数据索引加入集合

            ArrayList<Integer> resIndexList = new ArrayList<>();
            resIndexList.add(mid);

            //向mid左边扫描，将所有与arr[mid]相同的数据放入集合中
            int temp = mid-1;
            while (temp >= 0 && arr[temp] == value) {
                resIndexList.add(temp);
                temp--;
            }

            //向mid右边扫描，将所有与arr[mid]相同的数据放入集合中
            temp = mid+1;
            while (temp <= arr.length - 1 && arr[temp] == value) {
                resIndexList.add(temp);
                temp++;
            }

            return resIndexList;

        }

    }