总目录：地址如下看总纲

https://www.jianshu.com/p/929ca9e209e8

1、介绍【前提有序】

二分查找又称折半查找，既从中间数开始找，然后根据比较结果，选择需要折半的一边出发，
再次折半，以此类推找出元素

2、设计思路（单数）

1. 、确定当前数组的下标 mid = (left + right)/2;
2. 、其次让需要查找的数 findVal 和 arr[mid] 比较
   (1) findVal > arr[mid] 说明要查找的数在 mid 右边，因此向右递归查找
   (2) findVal < arr[mid] 说明要查找的数在 mid 左边，因此向左递归查找
   (3) findVal = arr[mid] 说明找到，既返回
3. 、需要注意何时结束递归？
   (1)找到就结束
   (2)递归完整个数组，仍然没有找到 findVal，也需要结束递归 ，当 left > rigth 就是结束递归的条件

3、代码(单数版）：只返回一个

/**
     * 二分查找(单数版)
     * 
     * @param arr     原始数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 查找的值
     * @return
     */
    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、设计思路（多数）

1. 、找到第一个匹配的索引值 mid 的时候，不要马上返回
2. 、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
3. 、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回

5、代码（多数版）：找到几个返回几个

    /**
     * 二分查找(多数版)
     * 
     * @param arr     原始数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 查找的值
     * @return
     */
    public static List<Integer> binarySearchS(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];

        if (findVal > midVal) {
            // 右递归
            return binarySearchS(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            // 左递归
            return binarySearchS(arr, left, mid - 1, findVal);
        } else {
            // ****************以下代码才是和简单版的区别所在，以上都一样*******
            // 1、找到第一个匹配的索引值 mid 的时候，不要马上返回
            // 用于接受结果
            List<Integer> resIndexList = new ArrayList();

            // 2、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
            int temp = mid - 1;// 左递归起始索引
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;// 不满足，退出(固二分为有序，左边的第一个不相同，再找也是不同)
                } else {
                    // 加入，左移（再找）
                    resIndexList.add(temp);
                    temp -= 1;
                }
            }
            resIndexList.add(mid);

            // 3、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                } else {
                    resIndexList.add(temp);
                    temp += 1;
                }
            }
            return resIndexList;
        }
    }

6、最终完整代码

/**
 * title: 二分查找（单，多数版）
 * @author 阿K
 * 2020年12月22日 下午9:56:17 
 */
public class BinarySearch {

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

        int findVal = 1000;
        System.out.println(binarySearch(arr, 0, arr.length - 1, findVal));
        System.out.println(binarySearchS(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) {

        // 当 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;
        }
    }

    /**
     * 二分查找(多数版)
     * 
     * @param arr     原始数组
     * @param left    左边索引
     * @param right   右边索引
     * @param findVal 查找的值
     * @return
     */
    public static List<Integer> binarySearchS(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];

        if (findVal > midVal) {
            // 右递归
            return binarySearchS(arr, mid + 1, right, findVal);
        } else if (findVal < midVal) {
            // 左递归
            return binarySearchS(arr, left, mid - 1, findVal);
        } else {
            // ****************以下代码才是和简单版的区别所在，以上都一样*******
            // 1、找到第一个匹配的索引值 mid 的时候，不要马上返回
            // 用于接受结果
            List<Integer> resIndexList = new ArrayList();

            // 2、向 mid 索引值 的左边扫描，将所有与 findVal 相等的元素 的下标 索引返回
            int temp = mid - 1;// 左递归起始索引
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    break;// 不满足，退出(固二分为有序，左边的第一个不相同，再找也是不同)
                } else {
                    // 加入，左移（再找）
                    resIndexList.add(temp);
                    temp -= 1;
                }
            }
            resIndexList.add(mid);

            // 3、向 mid 索引值 的右边扫描，将所有与 findVal 相等的元素 的下标 索引返回
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    break;
                } else {
                    resIndexList.add(temp);
                    temp += 1;
                }
            }
            return resIndexList;
        }
    }
}