Dada una array ordenada y un valor objetivo, encuentre el primer elemento que sea estrictamente mayor que el elemento dado.
Ejemplos:
Input : arr[] = {1, 2, 3, 5, 8, 12}
Target = 5
Output : 4 (Index of 8)
Input : {1, 2, 3, 5, 8, 12}
Target = 8
Output : 5 (Index of 12)
Input : {1, 2, 3, 5, 8, 12}
Target = 15
Output : -1
Una solución simple es recorrer linealmente la array dada y encontrar el primer elemento que sea estrictamente mayor. Si no existe tal elemento, devuelva -1.
Una solución eficiente es usar Binary Search . En una búsqueda binaria general, buscamos un valor que aparece en la array. A veces, sin embargo, necesitamos encontrar el primer elemento que sea mayor que un objetivo.
Para ver que este algoritmo es correcto, considere cada comparación que se realiza. Si encontramos un elemento que no es mayor que el elemento de destino, entonces no es posible que coincida con todo lo que está debajo de él, por lo que no hay necesidad de buscar esa región. Así podemos buscar la mitad derecha. Si encontramos un elemento que es más grande que el elemento en cuestión, entonces cualquier cosa después de él también debe ser más grande, por lo que no pueden ser el primer elemento que es más grande y no necesitamos buscarlos. El elemento medio es, por lo tanto, el último lugar posible en el que podría estar.
Tenga en cuenta que en cada iteración eliminamos al menos la mitad de los elementos restantes de la consideración. Si la rama superior se ejecuta, entonces todos los elementos en el rango [bajo, (bajo + alto) / 2] se descartan, lo que hace que perdamos piso ((bajo + alto) / 2) – bajo + 1 >= (bajo + alto) / 2 – bajo = (alto – bajo) / 2 elementos.
Si se ejecuta la rama inferior, todos los elementos del rango [(bajo + alto) / 2 + 1, alto] se descartan. Esto nos hace perder alto – piso (bajo + alto) / 2 + 1 >= alto – (bajo + alto) / 2 = (alto – bajo) / 2 elementos.
En consecuencia, terminaremos encontrando el primer elemento mayor que el objetivo en O(lg n) iteraciones de este proceso.
C++
// C++ program to find first element that
// is strictly greater than given target.
#include <iostream>
using namespace std;
int next(int arr[], int target, int end)
{
int start = 0;
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
// Move to right side if target is
// greater.
if (arr[mid] <= target)
start = mid + 1;
// Move left side.
else
{
ans = mid;
end = mid - 1;
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 5, 8, 12};
int n = sizeof(arr) / sizeof(arr[0]);
cout << next(arr, 8, n);
return 0;
}
// This code is contributed by sanjeev2552
Java
// Java program to find first element that
// is strictly greater than given target.
class GfG {
private static int next(int[] arr, int target)
{
int start = 0, end = arr.length - 1;
int ans = -1;
while (start <= end) {
int mid = (start + end) / 2;
// Move to right side if target is
// greater.
if (arr[mid] <= target) {
start = mid + 1;
}
// Move left side.
else {
ans = mid;
end = mid - 1;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 3, 5, 8, 12 };
System.out.println(next(arr, 8));
}
}
Python3
# Python program to find first element that # is strictly greater than given target. def next(arr, target): start = 0; end = len(arr) - 1; ans = -1; while (start <= end): mid = (start + end) // 2; # Move to right side if target is # greater. if (arr[mid] <= target): start = mid + 1; # Move left side. else: ans = mid; end = mid - 1; return ans; # Driver code if __name__ == '__main__': arr = [1, 2, 3, 5, 8, 12]; print(next(arr, 8)); # This code is contributed by 29AjayKumar
C#
// C# program to find first element that
// is strictly greater than given target.
using System;
class GfG
{
private static int next(int[] arr, int target)
{
int start = 0, end = arr.Length - 1;
int ans = -1;
while (start <= end)
{
int mid = (start + end) / 2;
// Move to right side if target is
// greater.
if (arr[mid] <= target)
{
start = mid + 1;
}
// Move left side.
else
{
ans = mid;
end = mid - 1;
}
}
return ans;
}
// Driver code
public static void Main()
{
int[] arr = { 1, 2, 3, 5, 8, 12 };
Console.WriteLine(next(arr, 8));
}
}
// This code is contributed by Code_Mech
PHP
<?php
// PHP program to find first element that
// is strictly greater than given target.
function next0($arr, $target)
{
$start = 0; $end = sizeof($arr) - 1;
$ans = -1;
while ($start <= $end)
{
$mid = (int)(($start + $end) / 2);
// Move to right side if target is
// greater.
if ($arr[$mid] <= $target)
{
$start = $mid + 1;
}
// Move left side.
else
{
$ans = $mid;
$end = $mid - 1;
}
}
return $ans;
}
// Driver code
{
$arr = array( 1, 2, 3, 5, 8, 12 );
echo(next0($arr, 8));
}
// This code is contributed by Code_Mech
?>
Javascript
<script>
// Javascript program to find first element that
// is strictly greater than given target.
function next(arr, target)
{
let start = 0, end = arr.length - 1;
let ans = -1;
while (start <= end)
{
let mid = parseInt((start + end) / 2, 10);
// Move to right side if target is
// greater.
if (arr[mid] <= target)
{
start = mid + 1;
}
// Move left side.
else
{
ans = mid;
end = mid - 1;
}
}
return ans;
}
// Driver code
let arr = [ 1, 2, 3, 5, 8, 12 ];
document.write(next(arr, 8));
// This code is contributed by decode2207
</script>
5
Publicación traducida automáticamente
Artículo escrito por TanishqSaluja y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA