Table of contents

Find the first and last position of an element in a sorted array

Given a sorted array nums and a target value target, find the starting and ending position of target in nums. If target is not found in the array, return [-1, -1].

Input-Output Examples

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]

Approach:

Technique: Binary Search

  1. Initialization: Define two functions, findFirst and findLast, to locate the first and last positions of target using binary search.
  2. Binary Search for First Position:
    • Initialize low to 0 and high to the length of the array minus one.
    • While low is less than or equal to high:
      • Calculate mid as the middle index.
      • If the element at mid is greater than or equal to target, move high to mid - 1.
      • If the element at mid is less than target, move low to mid + 1.
      • If nums[mid] equals target, update index and move high to mid - 1 to find the first occurrence.
  3. Binary Search for Last Position:
    • Similar to the first position search, but adjust the logic to find the last occurrence by moving low to mid + 1 when nums[mid] equals target.
  4. Combine Results: Return the results from findFirst and findLast.

C++ program to find the first and last position of an element in a sorted array

cpp
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int first = findFirst(nums, target);
        int last = findLast(nums, target);
        return {first, last};
    }

private:
    int findFirst(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        int index = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
            if (nums[mid] == target) index = mid;
        }
        return index;
    }

    int findLast(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1;
        int index = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if (nums[mid] == target) index = mid;
        }
        return index;
    }
};

Java program to find the first and last position of an element in a sorted array

cpp
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findLast(nums, target);
        return new int[] {first, last};
    }

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

    private int findLast(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        int index = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            if (nums[mid] == target) index = mid;
        }
        return index;
    }
}

Python program to find the first and last position of an element in a sorted array

python
from typing import List

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        first = self.findFirst(nums, target)
        last = self.findLast(nums, target)
        return [first, last]

    def findFirst(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        index = -1
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] >= target:
                high = mid - 1
            else:
                low = mid + 1
            if nums[mid] == target:
                index = mid
        return index

    def findLast(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1
        index = -1
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] <= target:
                low = mid + 1
            else:
                high = mid - 1
            if nums[mid] == target:
                index = mid
        return index

DSA

Related Articles