34. Find First and Last Position of Element in Sorted Array

Problem Statement:

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.

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

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

Example 3:
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

Solution:
Algorithm:

1. Find the target value in the array.
2. If the target value is found,then find the first and last position of the target value.
3. If the target value is not found,return [-1,-1].
4. Return the result.

Code:

public class Solution {
    public int[] searchRange(int[] nums,int target){

        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] == target){
                result[0] = mid;
                result[1] = mid;
                break;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        if(result[0] == -1){
            return result;
        }
        int i = mid - 1;
        while(i >= 0 && nums[i] == target){
            result[0] = i;
            i--;
        }
        i = mid + 1;
        while(i < nums.length && nums[i] == target){
            result[1] = i;
            i++;
        }
        return result;
    }

}

Time Complexity:
O(log N)

Space Complexity:
O(1)