View Discussion
Improve Article
Save Article
View Discussion
Improve Article
Save Article
Given a sorted array arr[] with possibly duplicate elements, the task is to find indexes of the first and last occurrences of an element x in the given array.
Examples:
Input : arr[] = {1, 3, 5, 5, 5, 5, 67, 123, 125}, x = 5
Output : First Occurrence = 2
Last Occurrence = 5Input : arr[] = {1, 3, 5, 5, 5, 5, 7, 123, 125 }, x = 7
Output : First Occurrence = 6
Last Occurrence = 6
A Naive Approach:
The idea to solve this problem is iterate on the elements of given array and check given elements in an array and keep track of first and last occurrence of the found element’s index.
Below are the steps to implement the above idea:
- Run a for loop and for i = 0 to n-1
- Take first = -1 and last = -1
- When we find an element first time then we update first = i
- We always update last=i whenever we find the element.
- We print first and last.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
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";
}
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;
}
C
#include <stdio.h>
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");
}
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;
}
Java
import java.io.*;
class GFG {
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);
}
}
Python3
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")
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)
x = 8
findFirstAndLast(arr, n, x)
C#
using System;
class GFG {
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");
}
public static void Main()
{
int[] arr = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 8;
findFirstAndLast(arr, x);
}
}
PHP
<?php
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";
}
$arr = array(1, 2, 2, 2, 2, 3, 4,
7, 8, 8 );
$n = count($arr);
$x = 8;
findFirstAndLast($arr, $n, $x);
?>
Javascript
<script>
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);
</script>
Output
First Occurrence = 8 Last Occurrence = 9Time Complexity: O(n)
Auxiliary Space: O(1)
An efficient approach using binary search:
1. For the first occurrence of a number
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;
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
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;
}
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;
}
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;
}
C
#include <stdio.h>
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;
}
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;
}
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;
}
Java
import java.io.*;
class GFG {
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;
}
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
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
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
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))
C#
using System;
class GFG {
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;
}
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()
{
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));
}
}
PHP
<?php
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;
}
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;
}
}
$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);
?>
Javascript
<script>
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;
}
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;
}
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>");
</script>
Output
First Occurrence = 8 Last Occurrence = 9Time Complexity: O(log n)
Auxiliary Space: O(1)
An Iterative Implementation of Binary Search Solution :
- For the first occurrence, we will first find the index of the number and then search again in the left subarray as long as we are finding the number.
- For the last occurrence, we will first find the index of the number and then search again in the right subarray as long as we are finding the number
First occurrence:
- Do while low <= high:
- First, find the mid element
- Check if the arr[mid] > x then the first element will occur on the left side of mid. So, bring the high pointer to mid – 1
- Check if the arr[mid] < x then the first element will occur on the right side of mid. So, bring the low pointer to mid + 1
- If arr[mid] == x then this may be the first element. So, update the result to mid and move the high pointer to mid – 1.
- Return the result.
Last occurrence:
- Do while low <= high:
- First, find the mid element
- Check if the arr[mid] > x then the last element will occur on the left side of mid. So, bring the low pointer to mid – 1
- Check if the arr[mid] < x then the last element will occur on the right side of mid. So, bring the low pointer to mid + 1
- If arr[mid] == x then this may be the last element. So, update the result to mid and move the low pointer to mid + 1.
- Finally, Return the result.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int first(int arr[], int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
high = mid - 1;
}
}
return res;
}
int last(int arr[], int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
low = mid + 1;
}
}
return res;
}
int main()
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int n = sizeof(arr) / sizeof(int);
int x = 8;
cout << "First Occurrence = " << first(arr, x, n);
cout << "\nLast Occurrence = " << last(arr, x, n);
return 0;
}
C
#include <stdio.h>
int first(int arr[], int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
high = mid - 1;
}
}
return res;
}
int last(int arr[], int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
low = mid + 1;
}
}
return res;
}
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, x, n));
printf("\nLast Occurrence = %d\n", last(arr, x, n));
return 0;
}
Java
import java.util.*;
class GFG {
static int first(int arr[], int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
high = mid - 1;
}
}
return res;
}
static int last(int arr[], int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
low = mid + 1;
}
}
return res;
}
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, x, n));
System.out.println("Last Occurrence = "
+ last(arr, x, n));
}
}
Python3
def first(arr, x, n):
low = 0
high = n - 1
res = -1
while (low <= high):
mid = (low + high) // 2
if arr[mid] > x:
high = mid - 1
elif arr[mid] < x:
low = mid + 1
else:
res = mid
high = mid - 1
return res
def last(arr, x, n):
low = 0
high = n - 1
res = -1
while(low <= high):
mid = (low + high) // 2
if arr[mid] > x:
high = mid - 1
elif arr[mid] < x:
low = mid + 1
else:
res = mid
low = mid + 1
return res
arr = [1, 2, 2, 2, 2, 3, 4, 7, 8, 8]
n = len(arr)
x = 8
print("First Occurrence =", first(arr, x, n))
print("Last Occurrence =", last(arr, x, n))
C#
using System;
class GFG {
static int first(int[] arr, int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
high = mid - 1;
}
}
return res;
}
static int last(int[] arr, int x, int n)
{
int low = 0, high = n - 1, res = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else {
res = mid;
low = mid + 1;
}
}
return res;
}
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;
Console.WriteLine("First Occurrence = "
+ first(arr, x, n));
Console.WriteLine("Last Occurrence = "
+ last(arr, x, n));
}
}
Javascript
<script>
function first(arr, x, n)
{
let low = 0, high = n - 1, res = -1;
while (low <= high)
{
let mid = Math.floor((low + high) / 2);
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else
{
res = mid;
high = mid - 1;
}
}
return res;
}
function last(arr, x, n)
{
let low = 0, high = n - 1, res = -1;
while (low <= high)
{
let mid = Math.floor((low + high) / 2);
if (arr[mid] > x)
high = mid - 1;
else if (arr[mid] < x)
low = mid + 1;
else
{
res = mid;
low = mid + 1;
}
}
return res;
}
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, x, n),"</br>");
document.write("Last Occurrence = " + last(arr, x, n));
</script>
Output
First Occurrence = 8 Last Occurrence = 9Time Complexity:O(log n)
Auxiliary Space: O(1)
An approach using inbuilt functions:
Below is the implementation using an inbuilt function:
C++
#include <bits/stdc++.h>
using namespace std;
void findFirstAndLast(int arr[], int n, int x)
{
int first, last;
first = lower_bound(arr, arr + n, x) - arr;
last = upper_bound(arr, arr + n, x) - arr - 1;
if (first == n) {
first = -1;
last = -1;
}
cout << "First Occurrence = " << first
<< "\nLast Occurrence = " << last;
}
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;
}
Java
import java.util.ArrayList;
public class GFG {
public static int first(ArrayList list, int x)
{
return list.indexOf(x);
}
public static int last(ArrayList list, int x)
{
return list.lastIndexOf(x);
}
public static void main(String[] args)
{
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
ArrayList<Integer> clist = new ArrayList<>();
for (int i : arr)
clist.add(i);
int x = 8;
System.out.println("First Occurrence = "
+ first(clist, x));
System.out.println("Last Occurrence = "
+ last(clist, x));
}
}
Python
// Java program to find first and
// last occurrences of a number in a
// given sorted array
import java.io.*;
import java.util.*;
class GFG
{
// If x is present in arr[] then
// returns the index of FIRST & LAST
// occurrence of x in arr[0..n-1],
// otherwise returns -1
public static void first_last(ArrayList<Integer> arr, int x)
{
int first = arr.indexOf(x);
Collections.reverse(arr);
int last = arr.size() - 1 - arr.indexOf(x);
System.out.println("First Occurrence = " + first);
System.out.println("Last Occurrence = " + last);
}
public static void main (String[] args)
{
ArrayList<Integer> arr = new ArrayList<Integer>(10);
// using add() to initialize dice values
arr.add(1);
arr.add(2);
arr.add(2);
arr.add(2);
arr.add(2);
arr.add(3);
arr.add(4);
arr.add(7);
arr.add(8);
arr.add(8);
int x = 8;
first_last(arr, x);
}
}
// This code is contributed by kothavvsaakash
Output
First Occurrence = 8 Last Occurrence = 9Time Complexity: O(log n)
Auxiliary Space: O(1)
Extended Problem : Count number of occurrences in a sorted array
This article is contributed by DANISH_RAZA. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.