二分查找--变形问题

1.查找第一个等于给定值的元素

    public static int binarySearchFirst(int[] data, int x) {
        int low = 0, high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (data[mid] > x) {
                high = mid - 1;
            } else if (data[mid] < x) {
                low = mid + 1;
            } else {
                //判断是不是数组第一个数据，或者上一个数据是不是等于所要寻找数据
                if (mid == 0 || data[mid - 1] != x) {
                    return mid;
                }
                high = mid - 1;

            }
        }

        return -1;
    }

2.查找最后一个等于给定值的元素

    public static int binarySearchLast(int[] data, int x) {
        int low = 0, high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (data[mid] > x) {
                high = mid - 1;
            } else if (data[mid] < x) {
                low = mid + 1;
            } else {
                //判断是不是最后一个数组
                if (mid >= data.length -1 || data[mid + 1] != x) {
                    return mid;
                }
                low = mid + 1;

            }
        }

        return -1;
    }

3.查找第一个大于等于给定值的元素

    public static int binarySearchFirstGreaterThan(int[] data, int x) {
        int low = 0, high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (data[mid] >= x) {
                
                //找到大于等于给定值的数据，判断上一个元素是否满足条件
                if (mid == 0 || data[mid - 1] < x) {
                    return mid;
                }

                high = mid - 1;

            } else {
                low = mid + 1;
            }

        }

        return -1;

    }

4.查找最后一个小于等于给定值的元素

    public static int binarySearchLastLessThan(int[] data, int x) {
        int low = 0, high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);

            if (data[mid] <= x) {
                if (mid >= data.length -1 || data[mid + 1] > x) {
                    return mid;
                }
                low = mid + 1;
            } else {
                high = mid - 1;
            }

        }
        return -1;
    }

5.有序循环数组，4，5，6，1，2，3 查找给定值的下标

    //查找转折点，来确认所在数据，在数组区间下表范围
    public static int binarySearchLoop(int[] data, int x) {

        if (data.length == 0) {
            return -1;
        }

        //转折点为最大值点
        int point = searchPoint(data);
        if (data[point] == x) {
            return point;
        }

        //大于最大值，数据不在数组内
        if (data[point] < x) {
            return -1;
        }

        //如果小于首位数据元素，则在最高点右侧,否则在0-point之内，
        if (data[0] > x) {
            return binarySearch2(data, x, point + 1, data.length - 1);
        }
        return binarySearch2(data, x, 0, point - 1);

    }

    public static int searchPoint(int[] data) {
        //如果数组首位元素大于末尾元素，数组一定是顺序排序，转折点在数组末尾元素。
        if (data[0] < data[data.length - 1]) {
            return data.length - 1;
        }

        //如果存在low = high情况，返回high
        int low = 0, high = data.length - 1;
        while (low < high) {

            //如果该点数据大于low数据且，该点的下一个数据小于该点数据，则为转折点，由于low !=high，最少两个数据，point + 1不会越界
            int point = low + ((high - low) >> 1);
            if(data[point] >= data[low] ){
                if(data[point + 1] < data[point]){
                    return point;
                }
                low = point + 1;
            }else {

                high = point -1;
            }
        }

        //low == high处，只能选择low为转折点
        return high;

    }
    public static int binarySearch2(int[] data, int x, int low, int high) {
        if (low > high) {
            return -1;
        }

        int mid = low + ((high - low) >> 1);
        if (data[mid] == x) {
            return mid;
        } else if (data[mid] > x) {
            return binarySearch2(data, x, low, mid - 1);
        } else {
            return binarySearch2(data, x, mid + 1, high);
        }

    }