二分查找标准写法

朴素的二分查找

public static int binarySearch(int[] arr, int start, int end, int target) {
    int result = -1;
    while (start <= end) {
        int mid = start + (end - start) / 2;    //防止溢位
        if (arr[mid] > target)
            end = mid - 1;
        else if (arr[mid] < target)
            start = mid + 1;
        else {
            result = mid;
            break;
        }
    }
    return result;
}

查询左右边界的二分查找

当查询左边界的时候：lower设置为true

当查询右边界的时候：lower设置为false（注意，查询的index要减去1）

public int binarySearch(int[] nums, int target, boolean lower) {
    int left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

赏

谢谢你请我吃糖果

微信