0034 - Find First and Last Position of Element in Sorted Array

0034 - Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

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

You must write an algorithm with O(log n) runtime complexity.

Examples

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Input: nums = [], target = 0 Output: [-1,-1]

Constraints

0 <= nums.length <= 105 -109 <= nums[i] <= 109 nums is a non-decreasing array. -109 <= target <= 109

Java Solutiuon

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = {-1, -1};
		int lo = 0, hi = nums.length - 1;

        if(nums.length < 1) return res;
		while(nums[lo] < nums[hi]) {
			int mid = lo + (hi - lo)/2;
			if(nums[mid] > target) {
				hi = mid - 1;
			} else if(nums[mid] < target) {
				lo = mid + 1;
			} else {
				if(nums[lo] == nums[mid]) {
					hi--;
				}else {
					lo++;
				}
			}
		}
		if(nums[lo] == nums[hi] && nums[lo]== target) {
			res[0] = lo;
			res[1] = hi;
		}
		
		return res;
    }
}