Search for a Range

Given a sorted array of integers, find the starting and ending
position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3,
4].

二分法

说明

用两次二分查找分别找出左右边界

复杂度

时间 O(logN) 空间 O(1)

代码

public int[] searchRange(int[] nums, int target) {
    int[] res = {-1, -1};
    if (nums == null || nums.length == 0) {
        return res;
    }
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    int start = 0;
    int end = nums.length - 1;
    while(start <= end) {
        int mid = start + (end - start) / 2;
        if (nums[mid] > target) {
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }
    if (left <= end) {
        res[0] = left;
        res[1] = end;
    }
    return res;
}

Search Insert Position

Given a sorted array and a target value, return the index if the
target is found. If not, return the index where it would be if it were
inserted in order.

You may assume no duplicates in the array.

Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7
→ 4 [1,3,5,6], 0 → 0

二分法

复杂度

时间O(logn)，空间复杂度O(1)

代码

public int searchInsert(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}