Find First and Last Position of Element in Sorted Array

Difficulty: Easy, Asked in: Google, Amazon, Microsoft.

Key takeaway: An excellent problem to learn problem-solving using binary search. Here we apply binary search twice to improve the time complexity.

Let's understand the problem

Given an array of integers sorted in ascending order, write a program to find the first and last position of a given target value.

• If the target is not found in the array, return [-1, -1].
• We must design an algorithm with O(log n) time complexity.

Example 1

Input: A[] = [-1, 1, 2, 2, 2, 5, 6, 12, 12], target = 2

Output: First occurrence = 2, Last occurrence = 4.

Example 2

Input: A[] = [21, 32, 51, 70, 71], target = 70

Output: First occurrence = 3, Last occurrence = 3.

Discussed solution approaches

• Brute force approach  using linear search
• Efficient approach  by applying binary search twice

Brute force approach using linear search

Solution idea

One basic solution is to traverse the array linearly and track the index of the first and last occurrence of the target. This approach is inefficient because we did not take advantage of the sorted order property.

Solution steps

1. We take a constant size array firstLast[2] to store the first and last occurrence of the target element. We will store the first occurrence at firstLast[0] and the last occurrence at firstLast[1]. At the start, we initialize both values with -1.
2. Now we traverse the array linearly from i = 0 to n - 1 and update firstLast[0] when we encounter the target value for the first time. To keep track of the last occurrence, we keep updating the value of firstLast[1] every time when we encounter the target value.
3. By the end of the loop, we return the firstLast[] array.

Solution code C++

vector<int> firstLastOccurence(int A[], int n, int target)
{
    vector<int> firstLast = {-1, -1};
    for (int i = 0; i < n; i = i + 1)
    {
        if (A[i] == target)
        {
            if (firstLast[0] == -1)
                firstLast[0] = i;
            firstLast[1] = i;
        }
    }
    return firstLast;
}

Solution code Python

def first_last_occurence(A, n, target):
    first_last = [-1, -1]
    for i in range(n):
        if A[i] == target:
            if first_last[0] == -1:
                first_last[0] = i
            first_last[1] = i
    return first_last

Solution analysis

We are running a single loop n time and doing O(1) operations at each iteration. Time complexity = n * O(1) = O(n). We are using constant extra space, so space complexity = O(1).

Efficient approach using binary search

Solution idea and steps

Now the critical questions are: Can we improve the time complexity further? Can we use the sorted order property to enhance the efficiency of searching? Let's think!

As we know, binary search will take O(logn) time to search the target value in the sorted array. But the given problem is different from the binary search problem because we need to search for two occurrences of the target element. So, how can we modify the standard binary search algorithm to solve it? Think.

The idea is to use binary search twice. We use the first binary search to find the first occurrence of the target, and the second binary search to find the last occurrence of the target. Let’s design an algorithm for both steps separately.

Binary search for finding the first occurrence

Let's use the iterative binary search! We first initialize low = 0 and high = n - 1 to track the left and right ends. Now we run a loop till low ≤ high:

1. We calculate mid, i.e. mid = low + (high - low)/2.
2. Now we compare the value at mid with the target. The middle element will be the first occurrence in two situations: 1) When the first occurrence is present somewhere in the middle i.e. target == A[mid] and target > A[mid - 1] 2) when the first occurrence is present at the first position i.e. mid == 0 and A[mid] == target. In both situations, we return the mid-index as the first occurrence.
3. If (target > A[mid]), we search for the first occurrence in the right part because all values in the left part are less than the target. Update low = mid + 1.
4. If both conditions are not satisfied, we need to search for the first occurrence in the left part (Think). We update high = mid - 1.
5. If we did not find the target value by the end of the loop, we return -1.

Pseudocode to find the first occurrence

int findFirstOccurrence(int A[], int n, int target)
{
    int low = 0, high = n - 1
    while (low <= high)
    {
        int mid = low + (high - low)/2
        if ((mid == 0 || A[mid - 1] < target) && A[mid] == target)
            return mid
        else if (target > A[mid])    
            low = mid + 1
        else
            high = mid - 1
    }
    return -1
}

Binary search for finding the last occurrence

Similarly, to find the last occurrence, we also modify the binary search algorithm. For this, we first initialize low = 0 and high = n - 1 to track the left and right ends. Now we run a loop until low ≤ high:

1. We calculate mid i.e. mid = low + (high - low)/2.
2. Next, we compare the value at mid with the target. The mid element will be the last occurrence in two situations: 1) When the last occurrence is present somewhere in the middle i.e. target == A[mid] and target < A[mid + 1] 2) When the last occurrence is at the last position i.e. mid == n - 1 and A[mid] == target.
3. If (target < A[mid]), we search for the last occurrence in the left part because all values in the right part are greater than the target. Update high= mid - 1.
4. If both conditions are not satisfied, we search for the last occurrence in the right part (Think). Update low = mid + 1.
5. By the end of the loop, if we did not find the target value, return -1.

Pseudocode to find the last occurrence

int findLastOccurrence(int A[], int n, int target)
{
    int low = 0, high = n - 1
    while (low <= high)
    {
        int mid = low + (high - low)/2
        if ((mid == n - 1 || A[mid + 1] > target) && A[mid] == target)
            return mid
        else if (target < A[mid])    
            high = mid - 1
        else
            low = mid + 1
    }
    return -1
}

Complete implementation code C++

int findLastOccurrence(int A[], int n, int target)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if ((mid == n - 1 || A[mid + 1] > target) && A[mid] == target)
            return mid;
        else if (target < A[mid])    
            high = mid - 1;
        else
            low = mid + 1;
    }
    return -1;
}

int findFirstOccurrence(int A[], int n, int target)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if ((mid == 0 || A[mid - 1] < target) && A[mid] == target)
            return mid;
        else if (target > A[mid])    
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1;
}

vector<int> findFirstLastOccurrence(int A[], int n, int target)
{
    vector<int> firstLast = {-1, -1};
    firstLast[0] = findFirstOccurrence(A, n, target);
    firstLast[1] = findLastOccurrence(A, n, target);
    return firstLast;
}

Complete implementation code Python

def find_last_occurrence(A, n, target):
    low = 0
    high = n - 1
    while low <= high:
        mid = low + (high - low) // 2
        if (mid == n - 1 or A[mid + 1] > target) and A[mid] == target:
            return mid
        elif target < A[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def find_first_occurrence(A, n, target):
    low = 0
    high = n - 1
    while low <= high:
        mid = low + (high - low) // 2
        if (mid == 0 or A[mid - 1] < target) and A[mid] == target:
            return mid
        elif target > A[mid]:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def find_first_last_occurrence(A, n, target):
    first_last = [-1, -1]
    first_last[0] = find_first_occurrence(A, n, target)
    first_last[1] = find_last_occurrence(A, n, target)
    return first_last

Solution analysis

Inside the function firstLastOccurrence(A[], n, target), we are doing some constant extra operations and applying binary search twice. Time complexity = O(1) + Time complexity to search first occurrence + Time complexity to search last occurrence = O(1) + O(logn) + O(logn) = O(log n).

We are using the implementation of iterative binary search, which takes O(1) extra space. Space complexity = O(1)

Critical ideas to think!

• Can we solve this problem using a single binary search?
• How can we implement the above approach using a recursive binary search? What will be the space complexity?
• How can we find the first and last occurrences of a target value in an unsorted array? What will be the various approaches and their time and space complexities?
• How can we find the first and last occurrence of a target in a sorted and rotated array?
• How can we find the kth occurrence of the target? Suppose the target is appearing m times and m > k.

Comparisons of time and space complexities

• Using linear search: Time = O(n), Space = O(1).
• Using binary search: Time = O(logn), Space = O(1).

Coding problems to practice using binary search

• Find maximum in bitonic array
• Min in rotated and sorted array
• Search in a sorted matrix
• Median of sorted arrays
• Find square root
• Find peak element in array
• Find smallest letter greater than target
• Search in rotated sorted array

Thanks to Navtosh for his contribution in creating the first version of this content. If you have any queries or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!