Find First and Last Position of Element in Sorted Array

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

Key takeaway: This is an excellent interview problem to learn problem-solving using binary search. We are applying binary search twice to improve the time complexity over brute force approach.

Let's understand the problem

Given an array of integers sorted in ascending order, write a code 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

The straightforward approach is to traverse the array and track index of the first and last occurrence of target. This approach is inefficient because we did not take advantage of the fact that given array is sorted.

Solution steps

  1. Take an extra constant size array firstLast[2] to store the first and last occurrence of target element. We will store the first occurrence at firstLast[0] and the last occurrence at firstLast[1]. At 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 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 target value.
  3. By the end of loop, we return firstLast[] array.

Solution pseudocode

int[] firstLastOccurence(int A[], int n, int target)
{
    int firstLast[2] = [-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 analysis

We are running a single loop n time and doing O(1) operation 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 critical questions are: Can we improve the time complexity further? Can we use the sorted order property to enhance efficiency of searching?

As we already know,binary search works perfectly for searching any element in the sorted array. It would take O(logn) time to search the target value. But the given problem is different from the binary search problem, where we need to search two occurrences of the target element. So, how do we modify the standard binary search algorithm to solve it? Think.

The idea is simple: We can use binary search twice to solve the problem. The first binary search for finding the first occurrence of target and the second binary search for finding the last occurrence of target. Let’s design an algorithm for both steps separately.

Binary search for finding the first occurrence

Let's use 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:

  • Calculate mid i.e. mid = low + (high - low)/2
  • Now compare the value at mid with target. The middle element will be the first occurrence in two situations: 1) target == A[mid] and target > A[mid - 1] i.e. when first occurrence is present somewhere in the middle 2) mid == 0 and A[mid] == target i.e. when first occurrence is present at the first position. In both situations, we return mid-index as the first occurrence.

    if ((mid == 0 || A[mid - 1] < target) && A[mid] == target)
      return mid
  • If (target > A[mid]), we search the first occurrence in the right part because all values in the left part is less than target. Update low = mid + 1
  • If both conditions are not satisfied, we need to search for the first occurrence in left part (Think). We update high = mid -1
  • If we did not find target value by the end of 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, for finding the last occurrence, we also modify binary search algorithm. We first initialize low = 0 and high = n - 1 to track left and right ends during binary search loop. Now we run a loop till low ≤ high:

  • We calculate mid i.e. mid = low + (high - low)/2
  • Now compare value at mid with the target. The mid element will be the last occurrence in two situations: 1) target == A[mid] and target < A[mid + 1] i.e. when last occurrence is present somewhere in the middle 2) mid == n - 1 and A[mid] == target i.e. when last occurrence is at the last position.
if ( (mid == n - 1 || A[mid + 1] > target) && A[mid] == target)
    return mid
  • If (target < A[mid]), we need to search last occurrence in the left part because all values in the right part is less than target. Update high= mid - 1
  • If both conditions are not satisfied, we need to search for first occurrence in the right part (Think). Update low = mid +1
  • By the end of 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
}

Solution pseudocode

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

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?

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

Thanks to Navtosh Kumar for his contribution in creating the first version of the content. Enjoy learning, Enjoy coding, Enjoy algorithms!

Share feedback with us

More blogs to explore

Our weekly newsletter

Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.

© 2022 Code Algorithms Pvt. Ltd.

All rights reserved.