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

 

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
        if (nums == null || nums.length == 0) {
        	return res;
        }
        int start = 0;
        int end = nums.length-1;
        int pos = 0;
        while (start <= end) {
        	int mid = (start + end) / 2;
        	pos = mid;
        	if (target < nums[mid]) {
        		end = mid - 1;
        	} else if (target > nums[mid]) {
        		start = mid + 1;
        	} else {
        		res[0] = pos;
        		res[1] = pos;
        		break;
        	}
        }
        if (nums[pos] != target) {
        	return res;
        }
        int newStart = pos;
        int newEnd = nums.length-1;
        while (newStart <= newEnd) {
        	int mid = (newStart + newEnd) / 2;
        	if (target == nums[mid]) {
        		newStart = mid + 1;
        	} else {
        		newEnd = mid - 1;
        	}
        }
        res[1] = newEnd;
        newStart = 0;
        newEnd = pos;
        while (newStart <= newEnd) {
        	int mid = (newStart + newEnd) / 2;
        	if (target == nums[mid]) {
        		newEnd = mid - 1;
        	} else {
        		newStart = mid + 1;
        	}
        }
        res[0] = newStart;
        return res;
    }
}