/**
     * 1.循环退出条件是 low <= high，而不是 low < high。
     * 2.mid = (low + high) / 2这种写法，在 low 和 high 比较大时，两者之和可能会溢出。
     *    改进的方法是将 mid 的计算方式写成 low + (high - low) / 2， 转化成位运算 low+((high-low)>>1) 更佳。
     * 3.low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。
     *    比如，当 high=3，low=3 时，如果 a[3] 不等于 value，就会导致一直循环不退出。
     * 时间复杂度为 O(logn)
     * @param arr
     * @param n
     * @param value
     * @return
     */
    public int bsearch(int[] arr, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;   // (low + high) / 2, 可能会发生溢出
            if (arr[mid] > value ) {            // 中间值 > 目标值, 往左边找, mid - 1
                high = mid - 1;
            } else if (arr[mid] < value) {      // 中间值 < 目标值, 往右边找, mid + 1
                low = mid + 1;
            } else {                            // 中间值 == 目标值
                return mid;
            }
        }
        return -1;
    }

    /**
     * 2. 二分查找的递归实现
     * @param arr
     * @param n
     * @param value
     * @return
     */
    public int bsearch_recurse(int[] arr, int n, int value) {
        return recursive(arr, 0, n - 1, value);
    }
    private int recursive(int[] arr, int low, int high, int value) {
        if (low > high) return -1;
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > value) {
            return recursive(arr, low, mid - 1, value);
        } else if (arr[mid] < value) {
            return recursive(arr, mid + 1, high, value);
        } else {
            return mid;
        }
    }

1000w 个 8字节整数的中查找某个整数是否存在，且内存占用不超过100M ？ 
1、由于内存限制，存储一个整数需要8字节，也就是 64 bit。此时是否可以考虑bitmap这样的数据结构，也就是每个整数就是一个索引下标，
    对于每一个索引bit，1 表示存在，0 表示不存在。同时考虑到整数的数据范围，8字节整数的范围太大，这是需要考虑压缩的问题，
    压缩方案可以参考 RoaringBitmap 的压缩方式。
2、我们要解决的问题，也就是判断某个元素是否属于某个集合的问题。这里是否可以和出题方探讨是否严格要求100%判断正确。
    在允许很小误差概率的情景下（比如判断是否在垃圾邮件地址黑名单中），可以考虑 BloomFilter 。
BloomFilter 存储空间更加高效。1000w数据、0.1%的误差下需要的内存仅为 17.14M 
时间复杂度上，上面两种都是 hashmap的变种，因此为 O(1)。


1000万数中快速查找某个整数，考虑用数组下标来存储数据，一个bit位来存储标记。
第一次排序的时候能得到这组数的最大值和最小值。 
假如最小是5，最大是2000万。那我们定义一个字节数组Byte arr[2000万]，因为我只需要打标记，
所以一个bit能存下标记，一个byte能存8个数。只需要2MB多一点就能存2000万个数的状态（存在还是不存在）
先把这1000万个数存进去，用数x/8得到下标。用数x%8得到余数，因为每8个数一组得到的数组下标相同，所以还需要通过余数来确定具体是哪一个数。
之后开始设置状态，从低位到高位，每一位代表一个数的状态，case0到7，每一次设置当下号码的状态时，先用按位于计算把其他不相关位置为1，当前位置为0，然后按位或对当前位置设置状态。
存在就设置位1 ，不存在就设置位0
上述操作执行完之后，就支持任意查找了。只需要输入一个数x，我就能立刻通过x/8和x%8得到当前这个数的位置，然后把这个位置的状态位数字取出来。如果是1表示存在，如果是0表示不存在。

    /**
     * 变体一: 查找第一个值等于给定值的元素
     * @param arr
     * @param n
     * @param value
     * @return
     */
    public int bsearch1(int arr[], int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] > value) {
                high = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == 0) || (arr[mid - 1] != value)) return mid;
                else high = mid -1;// 如果 arr[mid - 1] == value, 说明mid不是第一个下标值, 继续往左 查找
            }
        }
        return -1;
    }

    /**
     * 变体二：查找最后一个值等于给定值的元素
     * @param arr
     * @param n
     * @param value
     * @return
     */
    public int bsearch2(int arr[], int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] > value) {
                high = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                if ((mid == n - 1) || (arr[mid + 1] != value)) return mid;
                else low = mid + 1; // 如果 arr[mid + 1] == value, 说明mid不是最后一个下标值, 继续往右 查找
            }
        }
        return -1;
    }

    /**
     * 变体三：查找第一个大于等于给定值的元素
     * @param arr
     * @param n
     * @param value
     * @return
     */
    public int bsearch3(int arr[], int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] >= value) {
                if ((mid == 0) || (arr[mid - 1] < value)) return mid;
                else high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 变体四：查找最后一个小于等于给定值的元素
     * @param arr
     * @param n
     * @param value
     * @return
     */
    public int bsearch4(int[] arr, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] > value) {
                high = mid - 1;
            } else {
                if ((mid == n - 1) || (arr[mid + 1] > value)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }