An Iterative Implementation of Binary Search Solution

An efficient approach using binary search:

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 high 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.

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 x, int n)
{
    int low = 0, high = n - 1, res = -1;
    while (low <= high) {
 
        // Normal Binary Search Logic
        int mid = (low + high) / 2;
 
        if (arr[mid] > x)
            high = mid - 1;
        else if (arr[mid] < x)
            low = mid + 1;
 
        // If arr[mid] is same as x, we
        // update res and move to the left
        // half.
        else {
            res = mid;
            high = mid - 1;
        }
    }
    return res;
}
 
/* 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 x, int n)
{
    int low = 0, high = n - 1, res = -1;
    while (low <= high) {
 
        // Normal Binary Search Logic
        int mid = (low + high) / 2;
 
        if (arr[mid] > x)
            high = mid - 1;
        else if (arr[mid] < x)
            low = mid + 1;
 
        // If arr[mid] is same as x, we
        // update res and move to the right
        // half.
        else {
            res = mid;
            low = mid + 1;
        }
    }
    return res;
}
 
// 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;
    cout << "First Occurrence = " << first(arr, x, n);
    cout << "\nLast Occurrence = " << last(arr, x, n);
 
    return 0;
}
 
// This code is contributed by shivanisinghss2110

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 x, int n)
{
    int low = 0, high = n - 1, res = -1;
    while (low <= high) {
        // Normal Binary Search Logic
        int mid = (low + high) / 2;
        if (arr[mid] > x)
            high = mid - 1;
        else if (arr[mid] < x)
            low = mid + 1;
 
        // If arr[mid] is same as x, we
        // update res and move to the left
        // half.
        else {
            res = mid;
            high = mid - 1;
        }
    }
    return res;
}
 
/* 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 x, int n)
{
    int low = 0, high = n - 1, res = -1;
    while (low <= high) {
        // Normal Binary Search Logic
        int mid = (low + high) / 2;
        if (arr[mid] > x)
            high = mid - 1;
        else if (arr[mid] < x)
            low = mid + 1;
 
        // If arr[mid] is same as x, we
        // update res and move to the right
        // half.
        else {
            res = mid;
            low = mid + 1;
        }
    }
    return res;
}
 
// 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, x, n));
    printf("\nLast Occurrence = %d\n", last(arr, x, n));
 
    return 0;
}

Java

// Java program to find first
// and last occurrences of a
// number in a given sorted array
import java.util.*;
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
    static int first(int arr[], int x, int n)
    {
        int low = 0, high = n - 1, res = -1;
        while (low <= high) {
            // Normal Binary Search Logic
            int mid = (low + high) / 2;
            if (arr[mid] > x)
                high = mid - 1;
            else if (arr[mid] < x)
                low = mid + 1;
 
            // If arr[mid] is same as
            // x, we update res and
            // move to the left half.
            else {
                res = mid;
                high = mid - 1;
            }
        }
        return res;
    }
 
    // If x is present in arr[] then returns
    // the index of LAST occurrence of x in
    // arr[0..n-1], otherwise returns -1
    static int last(int arr[], int x, int n)
    {
        int low = 0, high = n - 1, res = -1;
        while (low <= high) {
            // Normal Binary Search Logic
            int mid = (low + high) / 2;
            if (arr[mid] > x)
                high = mid - 1;
            else if (arr[mid] < x)
                low = mid + 1;
 
            // If arr[mid] is same as x,
            // we update res and move to
            // the right half.
            else {
                res = mid;
                low = mid + 1;
            }
        }
        return res;
    }
 
    // Driver program
    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));
    }
}
 
// This code is contributed by Chitranayal

Python3

# Python3 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, x, n):
 
    low = 0
    high = n - 1
    res = -1
 
    while (low <= high):
 
        # Normal Binary Search Logic
        mid = (low + high) // 2
 
        if arr[mid] > x:
            high = mid - 1
        elif arr[mid] < x:
            low = mid + 1
 
        # If arr[mid] is same as x, we
        # update res and move to the left
        # half.
        else:
            res = mid
            high = mid - 1
 
    return res
 
# If x is present in arr[] then returns
# the index of FIRST occurrence of x in
# arr[0..n-1], otherwise returns -1
 
 
def last(arr, x, n):
 
    low = 0
    high = n - 1
    res = -1
 
    while(low <= high):
 
        # Normal Binary Search Logic
        mid = (low + high) // 2
 
        if arr[mid] > x:
            high = mid - 1
        elif arr[mid] < x:
            low = mid + 1
 
        # If arr[mid] is same as x, we
        # update res and move to the Right
        # half.
        else:
            res = mid
            low = mid + 1
 
    return res
 
 
# Driver code
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))
 
# This code is contributed by Ediga_Manisha.

C#

// C# program to find first
// and last occurrences of a
// number in a 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
    static int first(int[] arr, int x, int n)
    {
        int low = 0, high = n - 1, res = -1;
        while (low <= high) {
            // Normal Binary Search Logic
            int mid = (low + high) / 2;
            if (arr[mid] > x)
                high = mid - 1;
            else if (arr[mid] < x)
                low = mid + 1;
 
            // If arr[mid] is same as
            // x, we update res and
            // move to the left half.
            else {
                res = mid;
                high = mid - 1;
            }
        }
        return res;
    }
 
    // If x is present in []arr then returns
    // the index of LAST occurrence of x in
    // arr[0..n-1], otherwise returns -1
    static int last(int[] arr, int x, int n)
    {
        int low = 0, high = n - 1, res = -1;
        while (low <= high) {
            // Normal Binary Search Logic
            int mid = (low + high) / 2;
            if (arr[mid] > x)
                high = mid - 1;
            else if (arr[mid] < x)
                low = mid + 1;
 
            // If arr[mid] is same as x,
            // we update res and move to
            // the right half.
            else {
                res = mid;
                low = mid + 1;
            }
        }
        return res;
    }
 
    // Driver program
    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));
    }
}
 
// This code is contributed by 29AjayKumar

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, x, n)
{
    let low = 0, high = n - 1, res = -1;
    while (low <= high) 
    {
         
        // Normal Binary Search Logic
        let mid = Math.floor((low + high) / 2);
         
        if (arr[mid] > x)
            high = mid - 1;
        else if (arr[mid] < x)
            low = mid + 1;
 
        // If arr[mid] is same as x, we
        // update res and move to the left
        // half.
        else
        {
            res = mid;
            high = mid - 1;
        }
    }
    return res;
}
 
/* 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, x, n)
{
    let low = 0, high = n - 1, res = -1;
    while (low <= high) 
    {
         
        // Normal Binary Search Logic
        let mid = Math.floor((low + high) / 2);
         
        if (arr[mid] > x)
            high = mid - 1;
        else if (arr[mid] < x)
            low = mid + 1;
 
        // If arr[mid] is same as x, we
        // update res and move to the right
        // half.
        else
        {
            res = mid;
            low = mid + 1;
        }
    }
    return res;
}
 
// Driver code
 
    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));
 
 
// This code is contributed by shinjanpatra
 
</script>

Output

First Occurrence = 8
Last Occurrence = 9

Time Complexity: O(log n)
Auxiliary Space: O(1)

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

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 = 5

Input : 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++

// 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)

Tags:

#Amazon #Binary Search #Arrays #DSA #Amazon #Arrays #Binary Search

An efficient approach using binary search:

An approach using inbuilt functions:

An Iterative Implementation of Binary Search Solution

C++

C

Java

Python3

C#

Javascript

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

C++

C

Java

Python3

C#

PHP

Javascript

Similar Reads