Encuentre la primera y la última posición de un elemento en una array ordenada – Part 1

Dada una array ordenada con elementos posiblemente duplicados, la tarea es encontrar índices de la primera y última aparición de un elemento x en la array dada. 

Ejemplos: 

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

El enfoque ingenuo consiste en ejecutar un bucle for y verificar los elementos dados en una array.  

1. Run a for loop and for i = 0 to n-1
2. Take first = -1 and last = -1 
3. When we find element first time then we update first = i 
4. We always update last=i whenever we find the element.
5. We print first and last.

Implementación:

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>
Producción

First Occurrence = 8
Last Occurrence = 9

Complejidad temporal: O(n) 
Espacio auxiliar: O(1)
 
Una solución eficiente a este problema es utilizar una búsqueda binaria. 

1. Para la primera aparición de un número 

  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. Por la última ocurrencia de un número 

  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;

Implementación:

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>
Producción

First Occurrence = 8    
Last Occurrence = 9

Complejidad de tiempo : O(log n) 
Espacio auxiliar : O(Log n) 

Complete Interview Preparation - GFG

Implementación iterativa de la solución de búsqueda binaria: 

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>
Producción

First Occurrence = 8
Last Occurrence = 9

Tiempo Complejidad : O(log n) 
Espacio Auxiliar : O(1) 

Usando ArrayList

Agregue todos los elementos de la array a ArrayList y usando el método indexOf() y lastIndexOf() encontraremos la primera posición y la última posición del elemento en la array.

Implementación:

Java

// Java program for the above approach
import java.util.ArrayList;
public class GFG {
    public static int first(ArrayList list, int x)
    {
        // return first occurrence index
        // of element x in ArrayList
        // using method indexOf()
        return list.indexOf(x);
    }
    public static int last(ArrayList list, int x)
    {
        // return last occurrence index
        // of element x in ArrayList
        // using method lastIndexOf()
        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<>();
  
        // adding elements of array to ArrayList
        for (int i : arr)
            clist.add(i);
        int x = 8;
  
        // displaying the first occurrence
        System.out.println("First Occurrence = "
                           + first(clist, x));
  
        // displaying the last occurrence
        System.out.println("Last Occurrence = "
                           + last(clist, x));
    }
}
Producción

First Occurrence = 8
Last Occurrence = 9

 Otro enfoque que utiliza las funciones STL de c ++ límite inferior y superior

Implementación:

C++

#include <bits/stdc++.h>
using namespace std;
  
void findFirstAndLast(int arr[], int n, int x)
{
    int first, last;
    // to store first occurrence
    first = lower_bound(arr, arr + n, x) - arr;
    // to store last occurrence
    last = upper_bound(arr, arr + n, x) - arr - 1;
  
    if (first == n) {
        first = -1;
        last = -1;
    }
    cout << "First Occurrence = " << first
         << "\nLast Occurrence = " << last;
}
  
// 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;
}
Producción

First Occurrence = 8
Last Occurrence = 9

Tiempo Complejidad : O(log n)
Espacio Auxiliar : O(1) 

Otro enfoque es usar la función «índice()» de Python3, que busca un elemento dado en la Lista dada y devuelve el índice de su primera aparición en la lista. Usando la función “index( )”, encontramos la Primera Ocurrencia, y usando la función “index( )” en la Lista invertida, encontramos la Última Ocurrencia.

Implementación:

Java

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

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 & LAST
# occurrence of x in arr[0..n-1],
# otherwise returns -1
def first_last(arr, x):
  first = arr.index(x)
  last = len(arr) - 1 - arr[::-1].index(x)
  print("First Occurrence =", first)
  print("Last Occurrence =", last)
    
  
# Driver code
arr = [ 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 ]
x = 8
first_last(arr, x); 
   
# This code is contributed by kothavvsaakash
Producción

First Occurrence = 8
Last Occurrence = 9

Problema extendido: cuente el número de ocurrencias en una array ordenada

Este artículo es una contribución de DANISH_RAZA . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *