Back to DSA

Find First and Last Position of Element in Sorted Array

easy
Acceptance: 56%
Binary Search

In a sorted integer array, find the first and last positions where a given target value occurs. If the target is not found, return [-1, -1]. Your algorithm must run in O(log n) time.

Examples

Example 1:
Input:nums = [1,3,3,3,5,7], target = 3
Output:[1,3]
Explanation: 3 first occurs at index 1 and last occurs at index 3.
Example 2:
Input:nums = [2,4,6,8], target = 5
Output:[-1,-1]
Explanation: 5 is absent from the array.

Hints

Related Problems

Longest Increasing SubsequencemediumSearch in Rotated Sorted ArraymediumFind Peak ElementmediumKoko Eating BananasmediumSplit Array Largest Sumhard
00:00
class Solution {
    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }

    private int findFirst(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) { result = mid; hi = mid - 1; }
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return result;
    }

    private int findLast(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) { result = mid; lo = mid + 1; }
            else if (nums[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return result;
    }
}
Time complexityO(log n)
Space complexityO(1)