二分查找也叫折半查找，前提是查找序列是有序的，它是一种效率较高的查找算法，时间复杂度为O(log2n)。常见的电路排查，就是利用二分查找的原理。

基于二分查找，如果数组中只有一个目标值，返回目标值的下标

/**
     * 二分查找,前提，数组有序
     *
     * @param arr
     * @param left
     * @param right
     * @param target
     * @return 返回目标值的下标
     */
    public static int binarySearch(int[] arr, int left, int right, int target) {
        
        int mid = (left + right) / 2;
        //如果left>rigth,则表示目标值不存在
        if (left > right) {
            return -1;
        }
        // 中间值更大，则往左找
        if (arr[mid] > target) {
            return binarySearch(arr, left, mid - 1, target);
        }
        // 中间值更小，则往右找
        else if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, right, target);
        } else {
            return mid;
        }
    }

基于二分查找，如果数组中有多个目标值，返回目标值的下标的list集合

主要是在找到目标值之后，在目标值左右做下一步的判断，如果条件符合，则添加到list集合中

public static List<Integer> binarySearch2(int[] arr, int left, int right, int target) {
        
        int mid = (left + right) / 2;
        
        if (left > right) {
            return new ArrayList<Integer>();
        }
        // 中间值更大，则往左找
        if (arr[mid] > target) {
            return binarySearch2(arr, left, mid - 1, target);
        }
        // 中间值更小，则往右找
        else if (arr[mid] < target) {
            return binarySearch2(arr, mid + 1, right, target);
        }
        //此时，因为数组是有序的，找目标值后进行左右判断
        else {
            
            List<Integer> list = new ArrayList<Integer>();
            
            //临时索引
            int tempIndex = mid - 1;
            
            //先往作为判断
            while (tempIndex >= 0 && target == arr[tempIndex]) {
                list.add(tempIndex);
                tempIndex--;
            }
            
            //此时添加最先找到的目标索引
            list.add(mid);
            
            //往右为判断
            while (tempIndex < arr.length && target == arr[tempIndex]) {
                list.add(tempIndex);
                tempIndex++;
            }
            
            return list;
        }
    }

用例测试

public static void main(String[] args) {
        //int[] arr = {1, 2, 3, 4, 5,7, 9};
        //int res = binarySearch(arr, 0, arr.length - 1, 10);
        //System.out.println(res);
        int[] arr = {1, 2, 3, 4, 5, 7,7,7, 9};
        List<Integer> res = binarySearch2(arr, 0, arr.length - 1, 7);
        System.out.println(res);
        
    }