Find first and last positions of an element in a sorted array

/ DSA / By SkylineWebZ

Spread the love

Skylinewebz

Finding indices of the earliest and last occurrences of an element x in a sorted array arr[] with maybe duplicate elements is the goal.

Example

Input : arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, x = 5
Output : First Occurrence = 2
              Last Occurrence = 5


Input : arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }, x = 7


Output : First Occurrence = 6
              Last Occurrence = 6

A naive method:

Iteratively on the elements of an array, check given elements in an array and record first and last occurrence of the index of the discovered element.

The following outlines the actions to carry out the aforementioned concept:

Run a for loop covering i = 0 through n-1.
First = -1; last = -1.
After discovering an element first time, we update first = i.
Every time we locate an element, we change last=i.
First and last is printed.

Here is the application of the aforementioned strategy:

C++

// C++ program to find first and last occurrence of
// an elements in given sorted array
#include <bits/stdc++.h>
using namespace std;

// Function for finding first and last occurrence
// of an elements
void findFirstAndLast(int arr[], int n, int x)
{
	int first = -1, last = -1;
	for (int i = 0; i < n; i++) {
		if (x != arr[i])
			continue;
		if (first == -1)
			first = i;
		last = i;
	}
	if (first != -1)
		cout << "First Occurrence = " << first
			<< "\nLast Occurrence = " << last;
	else
		cout << "Not Found";
}

// Driver code
int main()
{
	int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
	int n = sizeof(arr) / sizeof(int);
	int x = 8;
	findFirstAndLast(arr, n, x);
	return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

C

// C program to find first and last occurrence of
// an elements in given sorted array
#include <stdio.h>

// Function for finding first and last occurrence
// of an elements
void findFirstAndLast(int arr[], int n, int x)
{
	int first = -1, last = -1;
	for (int i = 0; i < n; i++) {
		if (x != arr[i])
			continue;
		if (first == -1)
			first = i;
		last = i;
	}
	if (first != -1)
		printf(
			"First Occurrence = %d \nLast Occurrence = %d",
			first, last);
	else
		printf("Not Found");
}

// Driver code
int main()
{
	int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
	int n = sizeof(arr) / sizeof(int);
	int x = 8;
	findFirstAndLast(arr, n, x);
	return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)

Java

// Java program to find first and last occurrence of
// an elements in given sorted array
import java.io.*;

class GFG {
	// Function for finding first and last occurrence
	// of an elements
	public static void findFirstAndLast(int arr[], int x)
	{
		int n = arr.length;
		int first = -1, last = -1;
		for (int i = 0; i < n; i++) {
			if (x != arr[i])
				continue;
			if (first == -1)
				first = i;
			last = i;
		}
		if (first != -1) {
			System.out.println("First Occurrence = "
							+ first);
			System.out.println("Last Occurrence = " + last);
		}
		else
			System.out.println("Not Found");
	}

	public static void main(String[] args)
	{
		int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
		int x = 8;
		findFirstAndLast(arr, x);
	}
}

// This code is contributed by Aditya Kumar (adityakumar129)

Python3

# Python 3 program to find first and
# last occurrence of an elements in
# given sorted array


# Function for finding first and last
# occurrence of an elements
def findFirstAndLast(arr, n, x):
	first = -1
	last = -1
	for i in range(0, n):
		if (x != arr[i]):
			continue
		if (first == -1):
			first = i
		last = i

	if (first != -1):
		print("First Occurrence = ", first,
			" \nLast Occurrence = ", last)
	else:
		print("Not Found")


# Driver code
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)
x = 8
findFirstAndLast(arr, n, x)


# This code is contributed by Nikita Tiwari.

C#

// C# program to find first and last
// occurrence of an elements in given
// sorted array
using System;

class GFG {

	// Function for finding first and
	// last occurrence of an elements
	static void findFirstAndLast(int[] arr, int x)
	{
		int n = arr.Length;
		int first = -1, last = -1;

		for (int i = 0; i < n; i++) {
			if (x != arr[i])
				continue;
			if (first == -1)
				first = i;
			last = i;
		}
		if (first != -1) {
			Console.WriteLine("First "
							+ "Occurrence = " + first);
			Console.Write("Last "
						+ "Occurrence = " + last);
		}
		else
			Console.Write("Not Found");
	}

	// Driver code
	public static void Main()
	{
		int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
		int x = 8;
		findFirstAndLast(arr, x);
	}
}

// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find first and last
// occurrence of an elements in given
// sorted array

// Function for finding first and last
// occurrence of an elements
function findFirstAndLast( $arr, $n, $x)
{
	$first = -1; $last = -1;
	for ( $i = 0; $i < $n; $i++)
	{
		if ($x != $arr[$i])
			continue;
		if ($first == -1)
			$first = $i;
		$last = $i;
	}
	if ($first != -1)
		echo "First Occurrence = ", $first,
			"\n", "\nLast Occurrence = ",
									$last;
	else
		echo "Not Found";
}

// Driver code
	$arr = array(1, 2, 2, 2, 2, 3, 4,
								7, 8, 8 );
	$n = count($arr);
	$x = 8;
	
	findFirstAndLast($arr, $n, $x);
	
// This code is contributed by anuj_67.
?>

JavaScript

<script>
// Javascript program to find first and last occurrence of
// an elements in given sorted array
	
	// Function for finding first and last occurrence
	// of an elements
	function findFirstAndLast(arr,x)
	{
		let n = arr.length;
		let first = -1, last = -1;
		for (let i = 0; i < n; i++) {
			if (x != arr[i])
				continue;
			if (first == -1)
				first = i;
			last = i;
		}
		if (first != -1) {
			document.write("First Occurrence = " + first + "<br>");
			document.write("Last Occurrence = " + last + "<br>");
		}
		else
			document.write("Not Found");
	}
	
	let arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ];
	let x = 8;
	findFirstAndLast(arr, x);
	
	// This code is contributed by avanitrachhadiya2155
</script>

Output

First Occurrence = 8
Last Occurrence = 9
Time Complexity: O(n) 
Auxiliary Space: O(1)

A binary search-based effective method:

For the first number occurrence

a) If (high >= low)
b) Calculate  mid = low + (high – low)/2;
c) If ((mid == 0 || x > arr[mid-1]) && arr[mid] == x)
        return mid;
d) Else if (x > arr[mid])
       return first(arr, (mid + 1), high, x, n);
e) Else
       return first(arr, low, (mid -1), x, n);
f) Otherwise return -1;

2. For the last occurrence of a number

a) if (high >= low)
b) calculate mid = low + (high – low)/2;
c)if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
        return mid;
d) else if(x < arr[mid])
       return last(arr, low, (mid -1), x, n);
e) else
      return last(arr, (mid + 1), high, x, n);      
f) otherwise return -1;

C++

// C++ program to find first and last occurrences of
// a number in a given sorted array
#include <bits/stdc++.h>
using namespace std;

/* if x is present in arr[] then returns the index of
FIRST occurrence of x in arr[0..n-1], otherwise
returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
	if (high >= low) {
		int mid = low + (high - low) / 2;
		if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
			return mid;
		else if (x > arr[mid])
			return first(arr, (mid + 1), high, x, n);
		else
			return first(arr, low, (mid - 1), x, n);
	}
	return -1;
}

/* if x is present in arr[] then returns the index of
LAST occurrence of x in arr[0..n-1], otherwise
returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
	if (high >= low) {
		int mid = low + (high - low) / 2;
		if ((mid == n - 1 || x < arr[mid + 1])
			&& arr[mid] == x)
			return mid;
		else if (x < arr[mid])
			return last(arr, low, (mid - 1), x, n);
		else
			return last(arr, (mid + 1), high, x, n);
	}
	return -1;
}

// Driver program
int main()
{
	int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
	int n = sizeof(arr) / sizeof(int);

	int x = 8;
	printf("First Occurrence = %d\t",
		first(arr, 0, n - 1, x, n));
	printf("\nLast Occurrence = %d\n",
		last(arr, 0, n - 1, x, n));
	return 0;
}

// This code is contributed by Sania Kumari Gupta
// (kriSania804)

C

// C program to find first and last occurrences of
// a number in a given sorted array
#include <stdio.h>

/* if x is present in arr[] then returns the index of
FIRST occurrence of x in arr[0..n-1], otherwise
returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
	if (high >= low) {
		int mid = low + (high - low) / 2;
		if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
			return mid;
		else if (x > arr[mid])
			return first(arr, (mid + 1), high, x, n);
		else
			return first(arr, low, (mid - 1), x, n);
	}
	return -1;
}

/* if x is present in arr[] then returns the index of
LAST occurrence of x in arr[0..n-1], otherwise
returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
	if (high >= low) {
		int mid = low + (high - low) / 2;
		if ((mid == n - 1 || x < arr[mid + 1])
			&& arr[mid] == x)
			return mid;
		else if (x < arr[mid])
			return last(arr, low, (mid - 1), x, n);
		else
			return last(arr, (mid + 1), high, x, n);
	}
	return -1;
}

// Driver program
int main()
{
	int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
	int n = sizeof(arr) / sizeof(int);

	int x = 8;
	printf("First Occurrence = %d\t",
		first(arr, 0, n - 1, x, n));
	printf("\nLast Occurrence = %d\n",
		last(arr, 0, n - 1, x, n));

	return 0;
}

// This code is contributed by Sania Kumari Gupta
// (kriSania804)

Java

// Java program to find first and last occurrence of
// an elements in given sorted array
import java.io.*;

class GFG {
	/* if x is present in arr[] then returns the index of
	FIRST occurrence of x in arr[0..n-1], otherwise
	returns -1 */
	public static int first(int arr[], int low, int high,
							int x, int n)
	{
		if (high >= low) {
			int mid = low + (high - low) / 2;
			if ((mid == 0 || x > arr[mid - 1])
				&& arr[mid] == x)
				return mid;
			else if (x > arr[mid])
				return first(arr, (mid + 1), high, x, n);
			else
				return first(arr, low, (mid - 1), x, n);
		}
		return -1;
	}

	/* if x is present in arr[] then returns the index of
	LAST occurrence of x in arr[0..n-1], otherwise
	returns -1 */
	public static int last(int arr[], int low, int high,
						int x, int n)
	{
		if (high >= low) {
			int mid = low + (high - low) / 2;
			if ((mid == n - 1 || x < arr[mid + 1])
				&& arr[mid] == x)
				return mid;
			else if (x < arr[mid])
				return last(arr, low, (mid - 1), x, n);
			else
				return last(arr, (mid + 1), high, x, n);
		}
		return -1;
	}

	public static void main(String[] args)
	{

		int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
		int n = arr.length;
		int x = 8;
		System.out.println("First Occurrence = "
						+ first(arr, 0, n - 1, x, n));
		System.out.println("Last Occurrence = "
						+ last(arr, 0, n - 1, x, n));
	}
}

Python3

# Python 3 program to find first and
# last occurrences of a number in
# a given sorted array

# if x is present in arr[] then
# returns the index of FIRST
# occurrence of x in arr[0..n-1],
# otherwise returns -1


def first(arr, low, high, x, n):
	if(high >= low):
		mid = low + (high - low) // 2
		if((mid == 0 or x > arr[mid - 1]) and arr[mid] == x):
			return mid
		elif(x > arr[mid]):
			return first(arr, (mid + 1), high, x, n)
		else:
			return first(arr, low, (mid - 1), x, n)

	return -1


# if x is present in arr[] then
# returns the index of LAST occurrence
# of x in arr[0..n-1], otherwise
# returns -1
def last(arr, low, high, x, n):
	if (high >= low):
		mid = low + (high - low) // 2
		if ((mid == n - 1 or x < arr[mid + 1]) and arr[mid] == x):
			return mid
		elif (x < arr[mid]):
			return last(arr, low, (mid - 1), x, n)
		else:
			return last(arr, (mid + 1), high, x, n)

	return -1


# Driver program
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)

x = 8
print("First Occurrence = ",
	first(arr, 0, n - 1, x, n))
print("Last Occurrence = ",
	last(arr, 0, n - 1, x, n))


# This code is contributed by Nikita Tiwari.

C#

// C# program to find first and last occurrence
// of an elements in given sorted array
using System;

class GFG {

	/* if x is present in arr[] then
	returns the index of FIRST
	occurrence of x in arr[0..n-1],
	otherwise returns -1 */
	public static int first(int[] arr, int low, int high,
							int x, int n)
	{
		if (high >= low) {
			int mid = low + (high - low) / 2;

			if ((mid == 0 || x > arr[mid - 1])
				&& arr[mid] == x)
				return mid;
			else if (x > arr[mid])
				return first(arr, (mid + 1), high, x, n);
			else
				return first(arr, low, (mid - 1), x, n);
		}

		return -1;
	}

	/* if x is present in arr[] then returns
	the index of LAST occurrence of x in
	arr[0..n-1], otherwise returns -1 */
	public static int last(int[] arr, int low, int high,
						int x, int n)
	{
		if (high >= low) {
			int mid = low + (high - low) / 2;

			if ((mid == n - 1 || x < arr[mid + 1])
				&& arr[mid] == x)
				return mid;
			else if (x < arr[mid])
				return last(arr, low, (mid - 1), x, n);
			else
				return last(arr, (mid + 1), high, x, n);
		}

		return -1;
	}

	// Driver code
	public static void Main()
	{

		int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
		int n = arr.Length;
		int x = 8;
		Console.WriteLine("First Occurrence = "
						+ first(arr, 0, n - 1, x, n));

		Console.Write("Last Occurrence = "
					+ last(arr, 0, n - 1, x, n));
	}
}

// This code is contributed by nitin mittal.

PHP

<?php
// PHP program to find first
// and last occurrences of a 
// number in a given sorted array

// if x is present in arr[] then
// returns the index of FIRST 
// occurrence of x in arr[0..n-1], 
// otherwise returns -1 
function first($arr, $low, $high, 
						$x, $n)
{
	if($high >= $low)
	{
		$mid = floor($low + ($high - $low) / 2);
		if(($mid == 0 or $x > $arr[$mid - 1]) 
						and $arr[$mid] == $x)
			return $mid;
		else if($x > $arr[$mid])
			return first($arr, ($mid + 1),
						$high, $x, $n);
		else
			return first($arr, $low, ($mid - 1),
										$x, $n);
	}
	return -1;
}


// if x is present in arr[] 
// then returns the index of
// LAST occurrence of x in 
// arr[0..n-1], otherwise
// returns -1 
function last($arr, $low, $high,
						$x, $n)
{
	if ($high >= $low)
	{
		$mid = floor($low + ($high - 
						$low) / 2);
		if (( $mid == $n - 1 or $x < 
			$arr[$mid + 1]) and
			$arr[$mid] == $x)
				return $mid;
		else if ($x < $arr[$mid])
			return last($arr, $low, 
			($mid - 1), $x, $n);
		else
			return last($arr, ($mid + 1), 
						$high, $x, $n);
	return -1;
	}
}

	// Driver Code
	$arr = array(1, 2, 2, 2, 2, 3, 4, 7, 8, 8);
	$n = count($arr);

	$x = 8;
	echo "First Occurrence = ",
		first($arr, 0, $n - 1, $x, $n), "\n";
	echo "Last Occurrence = ",
		last($arr, 0, $n - 1, $x, $n);

// This code is contributed by anuj_67
?>

JavaScript

<script>

// JavaScript program to find first and last occurrences of
// a number in a given sorted array


/* if x is present in arr then returns the index of
FIRST occurrence of x in arr[0..n-1], otherwise
returns -1 */
function first(arr,low,high,x,n)
{
	if (high >= low) {
		let mid = low + Math.floor((high - low) / 2);
		if ((mid == 0 || x > arr[mid - 1]) && arr[mid] == x)
			return mid;
		else if (x > arr[mid])
			return first(arr, (mid + 1), high, x, n);
		else
			return first(arr, low, (mid - 1), x, n);
	}
	return -1;
}

/* if x is present in arr then returns the index of
LAST occurrence of x in arr[0..n-1], otherwise
returns -1 */
function last(arr, low, high, x, n)
{
	if (high >= low) {
		let mid = low + Math.floor((high - low) / 2);
		if ((mid == n - 1 || x < arr[mid + 1]) && arr[mid] == x)
			return mid;
		else if (x < arr[mid])
			return last(arr, low, (mid - 1), x, n);
		else
			return last(arr, (mid + 1), high, x, n);
	}
	return -1;
}

// Driver program

	let arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ];
	let n = arr.length; 

	let x = 8;
	document.write("First Occurrence = " + first(arr, 0, n - 1, x, n),"</br>");
	console.log("Last Occurrence = " + last(arr, 0, n - 1, x, n),"</br>");

// code is contributed by shinjanpatra

</script>

Output

First Occurrence = 8    
Last Occurrence = 9
Time Complexity: O(log n) 
Auxiliary Space: O(log n), for recursion call stack