Binary Search

Find the First and Last Position of an Element in a Sorted Array

Rajeev SinghAlgorithms1 mins read

Find the First and Last Position of an Element in a Sorted Array

Problem Statement

Given an array of integers a sorted in ascending 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: a = [1, 4, 4, 10, 10, 15, 20], target = 10
Output: [3, 4]

Example 2:

Input: a = [1, 4, 4, 10, 10, 15, 20], target = 15
Output: [5, 5]

Example 3:

Input: a = [1, 4, 4, 10, 10, 15, 20], target = 0
Output: [-1, -1]

Binary Search to find the First and Last Position of an Element in a Sorted Array

Since the array is sorted, we can apply binary search to find the first and last position. We will use standard binary search implementation and make some modifications to it to find the first/last position of the element. Here is the solution approach for finding the first position of the element:

  • Initialize firstPosition to -1
  • if target = a[mid], we have found the target value so we update firstPosition to mid. But since we need to find the very first position of target, we need to check further in the left part of the array to see if the target is available at a lower position or not.
  • Rest of the approach is similar to binary search:
    • If target < a[mid], continue the search in the left side of the mid element.
    • Otherwise, continue the search in the right side of the mid element.
import java.util.Scanner;

class FirstLastPositionOfElement {
    private static int binarySearchFirstPosition(int[] a, int target) {
        int start = 0;
        int end = a.length-1;

        int firstPosition = -1;
        
        while(start <= end) {
            int mid = (start + end)/2;

            if(target == a[mid]) {
                // Found target, update firstPosition and move to the left to find a smaller position by setting end=mid-1
                firstPosition = mid;
                end = mid-1;
            } else if (target < a[mid]) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }

        return firstPosition;
    }

    private static int binarySearchLastPosition(int[] a, int target) {
        int start = 0;
        int end = a.length-1;

        int lastPosition = -1;
        while(start <= end) {
            int mid = (start + end)/2;

            if(target == a[mid]) {
                // Found target, update lastPosition and move to the right to find a higher position by setting start=mid+1
                lastPosition = mid;
                start = mid+1;
            } else if (target < a[mid]) {
                end = mid-1;
            } else {
                start = mid+1;
            }
        }

        return lastPosition;
    }

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);
        int n = keyboard.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
          a[i] = keyboard.nextInt(); 
        }
        int target = keyboard.nextInt();
        keyboard.close();

        int firstPosition = binarySearchFirstPosition(a, target);
        int lastPosition = binarySearchLastPosition(a, target);

        System.out.printf("First position = %d, Last position = %d%n", firstPosition, lastPosition);
    }
}
# Output
$ javac FirstLastPositionOfElement.java
$ java FirstLastPositionOfElement
7
1 4 4 10 10 15 20
10
First position = 3, Last position = 4


$ java FirstLastPositionOfElement
7
1 4 4 10 10 15 20
15
First position = 5, Last position = 5


$ java FirstLastPositionOfElement
7
1 4 4 10 10 15 20
0
First position = -1, Last position = -1