Suponga que tiene una array ordenada de números infinitos, ¿cómo buscaría un elemento en la array?
Fuente: Experiencia de entrevista de Amazon.
Dado que la array está ordenada, lo primero que se nos viene a la mente es la búsqueda binaria, pero el problema aquí es que no sabemos el tamaño de la array.
Si la array es infinita, eso significa que no tenemos límites adecuados para aplicar la búsqueda binaria. Entonces, para encontrar la posición de la clave, primero encontramos los límites y luego aplicamos el algoritmo de búsqueda binaria.
Deje que Low apunte al primer elemento y High apunte al segundo elemento de la array. Ahora compare la clave con el elemento de índice alto, ->
si es mayor que el elemento de índice alto, copie el índice alto en el índice bajo y duplique el índice alto.
->si es más pequeño, aplique la búsqueda binaria en los índices altos y bajos encontrados.
A continuación se muestran las implementaciones del algoritmo anterior.
C++
// C++ program to demonstrate working of an algorithm that finds
// an element in an array of infinite size
#include<bits/stdc++.h>
using namespace std;
// Simple binary search algorithm
int binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
// function takes an infinite size array and a key to be
// searched and returns its position if found else -1.
// We don't know size of arr[] and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
int findPos(int arr[], int key)
{
int l = 0, h = 1;
int val = arr[0];
// Find h to do binary search
while (val < key)
{
l = h; // store previous high
h = 2*h; // double high index
val = arr[h]; // update new val
}
// at this point we have updated low and
// high indices, Thus use binary search
// between them
return binarySearch(arr, l, h, key);
}
// Driver program
int main()
{
int arr[] = {3, 5, 7, 9, 10, 90, 100, 130,
140, 160, 170};
int ans = findPos(arr, 10);
if (ans==-1)
cout << "Element not found";
else
cout << "Element found at index " << ans;
return 0;
}
Java
// Java program to demonstrate working of
// an algorithm that finds an element in an
// array of infinite size
class Test
{
// Simple binary search algorithm
static int binarySearch(int arr[], int l, int r, int x)
{
if (r>=l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
// Method takes an infinite size array and a key to be
// searched and returns its position if found else -1.
// We don't know size of arr[] and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
static int findPos(int arr[],int key)
{
int l = 0, h = 1;
int val = arr[0];
// Find h to do binary search
while (val < key)
{
l = h; // store previous high
//check that 2*h doesn't exceeds array
//length to prevent ArrayOutOfBoundException
if(2*h < arr.length-1)
h = 2*h;
else
h = arr.length-1;
val = arr[h]; // update new val
}
// at this point we have updated low
// and high indices, thus use binary
// search between them
return binarySearch(arr, l, h, key);
}
// Driver method to test the above function
public static void main(String[] args)
{
int arr[] = new int[]{3, 5, 7, 9, 10, 90,
100, 130, 140, 160, 170};
int ans = findPos(arr,10);
if (ans==-1)
System.out.println("Element not found");
else
System.out.println("Element found at index " + ans);
}
}
Python3
# Python Program to demonstrate working of an algorithm that finds
# an element in an array of infinite size
# Binary search algorithm implementation
def binary_search(arr,l,r,x):
if r >= l:
mid = l+(r-l)//2
if arr[mid] == x:
return mid
if arr[mid] > x:
return binary_search(arr,l,mid-1,x)
return binary_search(arr,mid+1,r,x)
return -1
# function takes an infinite size array and a key to be
# searched and returns its position if found else -1.
# We don't know size of a[] and we can assume size to be
# infinite in this function.
# NOTE THAT THIS FUNCTION ASSUMES a[] TO BE OF INFINITE SIZE
# THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
def findPos(a, key):
l, h, val = 0, 1, arr[0]
# Find h to do binary search
while val < key:
l = h #store previous high
h = 2*h #double high index
val = arr[h] #update new val
# at this point we have updated low and high indices,
# thus use binary search between them
return binary_search(a, l, h, key)
# Driver function
arr = [3, 5, 7, 9, 10, 90, 100, 130, 140, 160, 170]
ans = findPos(arr,10)
if ans == -1:
print ("Element not found")
else:
print("Element found at index",ans)
C#
// C# program to demonstrate working of an
// algorithm that finds an element in an
// array of infinite size
using System;
class GFG {
// Simple binary search algorithm
static int binarySearch(int []arr, int l,
int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l,
mid-1, x);
return binarySearch(arr, mid+1,
r, x);
}
return -1;
}
// Method takes an infinite size array
// and a key to be searched and returns
// its position if found else -1. We
// don't know size of arr[] and we can
// assume size to be infinite in this
// function.
// NOTE THAT THIS FUNCTION ASSUMES
// arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX OUT
// OF BOUND CHECKING
static int findPos(int []arr,int key)
{
int l = 0, h = 1;
int val = arr[0];
// Find h to do binary search
while (val < key)
{
l = h; // store previous high
h = 2 * h;// double high index
val = arr[h]; // update new val
}
// at this point we have updated low
// and high indices, thus use binary
// search between them
return binarySearch(arr, l, h, key);
}
// Driver method to test the above
// function
public static void Main()
{
int []arr = new int[]{3, 5, 7, 9,
10, 90, 100, 130, 140, 160, 170};
int ans = findPos(arr, 10);
if (ans == -1)
Console.Write("Element not found");
else
Console.Write("Element found at "
+ "index " + ans);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to demonstrate working
// of an algorithm that finds an
// element in an array of infinite size
// Simple binary search algorithm
function binarySearch($arr, $l,
$r, $x)
{
if ($r >= $l)
{
$mid = $l + ($r - $l)/2;
if ($arr[$mid] == $x)
return $mid;
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
return binarySearch($arr, $mid + 1,
$r, $x);
}
return -1;
}
// function takes an infinite
// size array and a key to be
// searched and returns its
// position if found else -1.
// We don't know size of arr[]
// and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES
// arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX
// OUT OF BOUND CHECKING
function findPos( $arr, $key)
{
$l = 0; $h = 1;
$val = $arr[0];
// Find h to do binary search
while ($val < $key)
{
// store previous high
$l = $h;
// double high index
$h = 2 * $h;
// update new val
$val = $arr[$h];
}
// at this point we have
// updated low and high
// indices, Thus use binary
// search between them
return binarySearch($arr, $l,
$h, $key);
}
// Driver Code
$arr = array(3, 5, 7, 9, 10, 90, 100,
130, 140, 160, 170);
$ans = findPos($arr, 10);
if ($ans==-1)
echo "Element not found";
else
echo "Element found at index " , $ans;
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to demonstrate working of an algorithm that finds
// an element in an array of infinite size
// Simple binary search algorithm
function binarySearch(arr, l, r, x)
{
if (r>=l)
{
let mid = l + Math.floor((r - l)/2);
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
// function takes an infinite size array and a key to be
// searched and returns its position if found else -1.
// We don't know size of arr[] and we can assume size to be
// infinite in this function.
// NOTE THAT THIS FUNCTION ASSUMES arr[] TO BE OF INFINITE SIZE
// THEREFORE, THERE IS NO INDEX OUT OF BOUND CHECKING
function findPos(arr, key)
{
let l = 0, h = 1;
let val = arr[0];
// Find h to do binary search
while (val < key)
{
l = h; // store previous high
h = 2*h; // double high index
val = arr[h]; // update new val
}
// at this point we have updated low and
// high indices, Thus use binary search
// between them
return binarySearch(arr, l, h, key);
}
// Driver program
let arr = [3, 5, 7, 9, 10, 90, 100, 130,
140, 160, 170];
let ans = findPos(arr, 10);
if (ans==-1)
document.write("Element not found");
else
document.write("Element found at index " + ans);
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
Element found at index 4
Sea p la posición del elemento a buscar. El número de pasos para encontrar el índice alto ‘h’ es O (Log p). El valor de ‘h’ debe ser inferior a 2*p. El número de elementos entre h/2 y h debe ser O(p). Por lo tanto, la complejidad temporal del paso de búsqueda binaria también es O(Log p) y la complejidad temporal general es 2*O(Log p), que es O(Log p).
Este artículo es una contribución de Gaurav Sharma . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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