[LeetCode] Search for a Range (Java)

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].

Analysis

In fact, in this problem, we are going to use binary search to find the border of certain target, because there may be duplicate numbers. We can easily find the left border of certain target. And we can try to find the left border of target + 1. And check if it exists to determine the right border.

Code

public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] ret = {-1, -1};
        int start = 0;
        int end = A.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (A[mid] < target)
                start = mid + 1;
            else
                end = mid;
        }
        int low;
        if (A[start] != target)
            return ret;
        else
            low = start;
        start = 0;
        end = A.length - 1;
        while (start < end) {
            int mid = (start + end) / 2;
            if (A[mid] < target + 1)
                start = mid + 1;
            else
                end = mid;
        }
        int high = A[start] == target ? start : start - 1;
        ret[0] = low;
        ret[1] = high;
        return ret;
    }
}

public class Solution {

public int[] searchRange(int[] A, int target) {

int[] ret = {-1, -1};

int start = 0;

int end = A.length - 1;

while (start < end) {

int mid = (start + end) / 2;

if (A[mid] < target)

start = mid + 1;

else

end = mid;

}

int low;

if (A[start] != target)

return ret;

else

low = start;

start = 0;

end = A.length - 1;

while (start < end) {

int mid = (start + end) / 2;

if (A[mid] < target + 1)

start = mid + 1;

else

end = mid;

}

int high = A[start] == target ? start : start - 1;

ret[0] = low;

ret[1] = high;

return ret;

}

Complexity

It’s O(log n).