Skip to content

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

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

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]

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // base case 
        if (nums == null || nums.length == 0){
            return new int[]{-1,-1};
        }

        int left = 0;
        int right = nums.length - 1;
        int count = -1;

        while (left <= right){
            int mid = left + (right - left)/2;
            if (nums[mid] == target){
                count = mid;
                break;
            } else if (nums[mid] < target){
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }

        if (count == -1){
            return new int[]{-1,-1};
        }
        int first = count;
        int last = count;


        while((first != 0) && nums[first-1] == target){
            first = first -1;
        }

        while((last != nums.length-1) && nums[last+1] == target){
            last = last + 1;
        }

        return new int[]{first, last};

    }

}

// Time complexity: O(logN)
// Space complexity: O(1)