Dada una array no ordenada y un número x, encuentre un índice de la primera aparición de x cuando ordenamos la array. Si x no está presente, imprima -1.
Ejemplos:
Input : arr[] = {10, 30, 20, 50, 20}
x = 20
Output : 1
Sorted array is {10, 20, 20, 30, 50}
Input : arr[] = {10, 30, 20, 50, 20}
x = 60
Output : -1
60 is not present in array.
Una solución simple es ordenar primero la array y luego realizar una búsqueda binaria para encontrar la primera aparición .
C++
// C++ program to find index of first
// occurrence of x when array is sorted.
#include <bits/stdc++.h>
using namespace std;
int findFirst(int arr[], int n, int x)
{
sort(arr, arr + n);
// lower_bound returns iterator pointing to
// first element that does not compare less
// to x.
int* ptr = lower_bound(arr, arr + n, x);
// If x is not present return -1.
return (*ptr != x) ? -1 : (ptr - arr);
}
int main()
{
int x = 20, arr[] = { 10, 30, 20, 50, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findFirst(arr, n, x);
return 0;
}
Java
// Java program to find index of first
// occurrence of x when array is sorted.
import java.util.*;
class GFG {
static int findFirst(int arr[], int n, int x)
{
Arrays.sort(arr);
// lower_bound returns iterator pointing to
// first element that does not compare less
// to x.
int ptr = lowerBound(arr, 0, n, x);
// If x is not present return -1.
return (arr[ptr] != x) ? -1 : (ptr);
}
static int lowerBound(int[] a, int low, int high,
int element)
{
while (low < high) {
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Driver Code
public static void main(String[] args)
{
int x = 20, arr[] = { 10, 30, 20, 50, 20 };
int n = arr.length;
System.out.println(findFirst(arr, n, x));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to find index of first # occurrence of x when array is sorted. import math def findFirst(arr, n, x): arr.sort() # lower_bound returns iterator pointing to # first element that does not compare less # to x. ptr = lowerBound(arr, 0, n, x) # If x is not present return -1. return 1 if (ptr != x) else (ptr - arr) def lowerBound(a, low, high, element): while(low < high): middle = low + (high - low) // 2 if(element > a[middle]): low = middle + 1 else: high = middle return low # Driver Code if __name__ == '__main__': x = 20 arr = [10, 30, 20, 50, 20] n = len(arr) print(findFirst(arr, n, x)) # This code is contributed by Rajput-Ji
C#
// C# program to find index of first
// occurrence of x when array is sorted.
using System;
class GFG {
static int findFirst(int[] arr, int n, int x)
{
Array.Sort(arr);
// lower_bound returns iterator pointing to
// first element that does not compare less
// to x.
int ptr = lowerBound(arr, 0, n, x);
// If x is not present return -1.
return (arr[ptr] != x) ? -1 : (ptr);
}
static int lowerBound(int[] a, int low, int high,
int element)
{
while (low < high) {
int middle = low + (high - low) / 2;
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Driver Code
static public void Main()
{
int x = 20;
int[] arr = { 10, 30, 20, 50, 20 };
int n = arr.Length;
Console.Write(findFirst(arr, n, x));
}
}
// This code is contributed by ajit.
PHP
<?php
//PHP program to find index of first
// occurrence of x when array is sorted.
function findFirst( $arr, $n, $x)
{
sort($arr);
// lower_bound returns iterator pointing to
// first element that does not compare less
// to x.
$ptr = floor($arr);
// If x is not present return -1.
return ($ptr != $x)? 1 : ($ptr - $arr);
}
//Code driven
$x = 20;
$arr = array(10, 30, 20, 50, 20);
$n = sizeof($arr)/sizeof($arr[0]);
echo findFirst($arr, $n, $x);
#This code is contributed by Tushil.
?>
Javascript
<script>
// Javascript program to find index of first
// occurrence of x when array is sorted.
function findFirst(arr, n, x)
{
arr.sort();
// lower_bound returns iterator pointing
// to first element that does not compare
// less to x.
let ptr = lowerBound(arr, 0, n, x);
// If x is not present return -1.
return (arr[ptr] != x) ? -1 : (ptr);
}
function lowerBound(a, low, high, element)
{
while (low < high)
{
let middle = low + parseInt(
(high - low) / 2, 10);
if (element > a[middle])
low = middle + 1;
else
high = middle;
}
return low;
}
// Driver code
let x = 20;
let arr = [ 10, 30, 20, 50, 20 ];
let n = arr.length;
document.write(findFirst(arr, n, x));
// This code is contributed by mukesh07
</script>
Producción:
1
Complejidad de tiempo: O (n Log n)
Espacio Auxiliar: O(1)
Una solución eficiente es simplemente contar elementos más pequeños que x.
C++
// C++ program to find index of first
// occurrence of x when array is sorted.
#include <bits/stdc++.h>
using namespace std;
int findFirst(int arr[], int n, int x)
{
int count = 0;
bool isX = false;
for (int i = 0; i < n; i++) {
if (arr[i] == x)
isX = true;
else if (arr[i] < x)
count++;
}
return (isX == false) ? -1 : count;
}
int main()
{
int x = 20, arr[] = { 10, 30, 20, 50, 20 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findFirst(arr, n, x);
return 0;
}
Java
// Java program to find index of first
// occurrence of x when array is sorted.
public class GFG {
static int findFirst(int arr[], int n, int x)
{
int count = 0;
boolean isX = false;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
isX = true;
}
else if (arr[i] < x) {
count++;
}
}
return (isX == false) ? -1 : count;
}
// Driver main
public static void main(String[] args)
{
int x = 20, arr[] = { 10, 30, 20, 50, 20 };
int n = arr.length;
System.out.println(findFirst(arr, n, x));
}
}
/*This code is contributed by PrinciRaj1992*/
Python3
# Python 3 program to find index # of first occurrence of x when # array is sorted. def findFirst(arr, n, x): count = 0 isX = False for i in range(n): if (arr[i] == x): isX = True elif (arr[i] < x): count += 1 return -1 if(isX == False) else count # Driver Code if __name__ == "__main__": x = 20 arr = [10, 30, 20, 50, 20] n = len(arr) print(findFirst(arr, n, x)) # This code is contributed # by ChitraNayal
C#
// C# program to find index of first
// occurrence of x when array is sorted.
using System;
public class GFG {
static int findFirst(int[] arr, int n, int x)
{
int count = 0;
bool isX = false;
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
isX = true;
}
else if (arr[i] < x) {
count++;
}
}
return (isX == false) ? -1 : count;
}
// Driver main
public static void Main()
{
int x = 20;
int[] arr = { 10, 30, 20, 50, 20 };
int n = arr.Length;
Console.WriteLine(findFirst(arr, n, x));
}
}
/*This code is contributed by PrinciRaj1992*/
PHP
<?php
// PHP program to find index of first
// occurrence of x when array is sorted.
function findFirst($arr, $n, $x)
{
$count = 0;
$isX = false;
for ($i = 0; $i < $n; $i++)
{
if ($arr[$i] == $x)
$isX = true;
else if ($arr[$i] < $x)
$count++;
}
return ($isX == false)? -1 : $count;
}
// Driver Code
$x = 20;
$arr = array(10, 30, 20, 50, 20);
$n = sizeof($arr);
echo findFirst($arr, $n, $x);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// JavaScript program to find index of first
// occurrence of x when array is sorted.
function findFirst(arr, n, x)
{
var count = 0;
var isX = false;
for(var i = 0; i < n; i++)
{
if (arr[i] == x)
{
isX = true;
}
else if (arr[i] < x)
{
count++;
}
}
return (isX == false) ? -1 : count;
}
// Driver Code
var x = 20, arr = [ 10, 30, 20, 50, 20 ];
var n = arr.length;
document.write(findFirst(arr, n, x));
// This code is contributed by Khushboogoyal499
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar : O(1)