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