4_二分查找（原式 + 4种变式）

原式：最简单的二分查找

public static int search(int[] arr, int value) {
    int left=0;
    int right = arr.length - 1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] < value) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

注意1：求mid时，使用 int mid = left + ((right - left) >> 1); 代替 int mid = (right + left) / 2; 避免整数越界。

注意2：当数组中存在重复元素时，二分查找只能找出第一个满足相等条件的目标值。
举个例子：二分查找a[10]中的8，会找到a[7]，即第3个8。

4个变式问题

变式1：二分查找目标值的左侧边界

public static int searchFirst(int[] arr, int value) {
    int low = 0;
    int high = arr.length - 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 (arr[mid] == value) {
            // 若mid是数组第一个数时，表示找到了左边界
            // 若mid前一个数不是目标值，表示找到了左边界
            if (mid == 0 || arr[mid - 1] != value) {
                return mid;
            }
            // 若不满足条件，则左边界在[low,mid-1]区间
            else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

和原式二分查找的区别在于arr[mid] == value的情况：
在中间值等于目标值时，无法判断这个中间值是目标值左边界，所以要做以下判断：

1. mid==0→若mid是数组第一个数时，表示找到了左边界
2. arr[mid - 1] != value→若mid前一个数不是目标值，表示找到了左边界

若不满足以上两个条件，则左边界在[low,mid-1]区间

变式2：二分查找目标值的右侧边界

public static int searchLast(int[] arr, int value) {
    int low = 0;
    int high = arr.length - 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 (arr[mid] == value) {
            // 若mid是数组最后一个数时，表示找到了右边界
            // 若mid后一个数不是目标值，表示找到了右边界
            if (mid == arr.length - 1 || arr[mid + 1] != value) {
                return mid;
            }
            // 若不满足条件，则左边界在[mid+1,high]区间
            else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

与变式1同理，更改一下arr[mid] == value的判断即可。

变式3：查找第一个大于等于目标值的元素

public static int searchFirstGreaterOrEqual(int[] arr, int value) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] < value) {
            low = mid + 1;
        } else if (arr[mid] >= value) {
            // 若mid是数组第一个数时，表示找到了第一个大于等于目标值的元素
            // 若mid前一个数小于目标值，表示找到了第一个大于等于目标值的元素
            if (mid == 0 || arr[mid - 1] < value) {
                return mid;
            }
            // 若不满足条件，则第一个大于等于目标值的元素在[low,mid-1]区间
            else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

在arr[mid] >= value的情况下，无法判断这个中间值是第一个大于等于目标值的元素，所以要做以下判断：

1. mid==0→若mid是数组第一个数时，表示找到了第一个大于等于目标值的元素
2. arr[mid - 1] < value→若mid前一个数小于目标值，表示找到了第一个大于等于目标值的元素

若不满足以上两个条件，则第一个大于等于目标值的元素在[low,mid-1]区间

变式4：查找最后一个小于等于目标值的元素

public static int searchLastLessOrEqual(int[] arr, int value) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > value) {
            high = mid - 1;
        } else if (arr[mid] <= value) {
            // 若mid是数组最后一个数时，表示找到了最后一个小于等于目标值的元素
            // 若mid后一个数大于目标值，表示找到了最后一个小于等于目标值的元素
            if (mid == arr.length - 1 || arr[mid + 1] > value) {
                return mid;
            }
            // 若不满足条件，则最后一个小于等于目标值的元素在[mid+1,high]区间
            else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

与变式3同理，不做赘述。