El nombre de este algoritmo de búsqueda puede ser engañoso ya que funciona en tiempo O (Log n). El nombre proviene de la forma en que busca un elemento.
Given a sorted array, and an element x to be
searched, find position of x in the array.
Input: arr[] = {10, 20, 40, 45, 55}
x = 45
Output: Element found at index 3
Input: arr[] = {10, 15, 25, 45, 55}
x = 15
Output: Element found at index 1
Hemos discutido, búsqueda lineal , búsqueda binaria para este problema.
La búsqueda exponencial implica dos pasos:
- Encuentra el rango donde el elemento está presente
- Realice una búsqueda binaria en el rango encontrado anterior.
¿Cómo encontrar el rango donde el elemento puede estar presente?
La idea es comenzar con el tamaño de subarreglo 1, comparar su último elemento con x, luego probar el tamaño 2, luego 4 y así sucesivamente hasta que el último elemento de un subarreglo no sea mayor.
Una vez que encontramos un índice i (después de duplicar repetidamente i), sabemos que el elemento debe estar presente entre i/2 e i (¿Por qué i/2? porque no pudimos encontrar un valor mayor en la iteración anterior)
A continuación se muestran los implementaciones de los pasos anteriores.
C++
// C++ program to find an element x in a
// sorted array using Exponential search.
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int, int, int);
// Returns position of first occurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{
// If x is present at first location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return binarySearch(arr, i/2,
min(i, n-1), x);
}
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is
// present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then it
// can only be present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? cout <<"Element is not present in array"
: cout <<"Element is present at index " << result;
return 0;
}
// this code is contributed by shivanisinghss2110
C
// C++ program to find an element x in a
// sorted array using Exponential search.
#include <stdio.h>
#include <time.h>
#include <math.h>
#define min
int binarySearch(int arr[], int, int, int);
// Returns position of first occurrence of
// x in array
int exponentialSearch(int arr[], int n, int x)
{
// If x is present at first location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return binarySearch(arr, i/2,
min(i, n-1), x);
}
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is
// present, otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then it
// can only be present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid+1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver code
int main(void)
{
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int result = exponentialSearch(arr, n, x);
(result == -1)? printf("Element is not
present in array")
: printf("Element is present
at index %d",
result);
return 0;
}
Java
// Java program to
// find an element x in a
// sorted array using
// Exponential search.
import java.util.Arrays;
class GFG
{
// Returns position of
// first occurrence of
// x in array
static int exponentialSearch(int arr[],
int n, int x)
{
// If x is present at first location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return Arrays.binarySearch(arr, i/2,
Math.min(i, n-1), x);
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr,
arr.length, x);
System.out.println((result < 0) ?
"Element is not present in array" :
"Element is present at index " +
result);
}
}
Python3
# Python program to find an element x
# in a sorted array using Exponential Search
# A recursive binary search function returns
# location of x in given array arr[l..r] is
# present, otherwise -1
def binarySearch( arr, l, r, x):
if r >= l:
mid = l + ( r-l ) // 2
# If the element is present at
# the middle itself
if arr[mid] == x:
return mid
# If the element is smaller than mid,
# then it can only be present in the
# left subarray
if arr[mid] > x:
return binarySearch(arr, l,
mid - 1, x)
# Else he element can only be
# present in the right
return binarySearch(arr, mid + 1, r, x)
# We reach here if the element is not present
return -1
# Returns the position of first
# occurrence of x in array
def exponentialSearch(arr, n, x):
# IF x is present at first
# location itself
if arr[0] == x:
return 0
# Find range for binary search
# j by repeated doubling
i = 1
while i < n and arr[i] <= x:
i = i * 2
# Call binary search for the found range
return binarySearch( arr, i // 2,
min(i, n-1), x)
# Driver Code
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponentialSearch(arr, n, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))
# This code is contributed by Harshit Agrawal
C#
// C# program to find an element x in a
// sorted array using Exponential search.
using System;
class GFG {
// Returns position of first
// occurrence of x in array
static int exponentialSearch(int []arr,
int n, int x)
{
// If x is present at
// first location itself
if (arr[0] == x)
return 0;
// Find range for binary search
// by repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i * 2;
// Call binary search for
// the found range.
return binarySearch(arr, i/2,
Math.Min(i, n - 1), x);
}
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
static int binarySearch(int []arr, int l,
int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
// If the element is present
// at the middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than
// mid, then it can only be
// present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only
// be present in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element
// is not present in array
return -1;
}
// Driver code
public static void Main()
{
int []arr = {2, 3, 4, 10, 40};
int n = arr.Length;
int x = 10;
int result = exponentialSearch(arr, n, x);
if (result == -1)
Console.Write("Element is not
present in array");
else
Console.Write("Element is
present at index "
+ result);
}
}
// This code is contributed by Smitha
PHP
<?php
// PHP program to find an element x in a
// sorted array using Exponential search.
// Returns position of first
// occurrence of x in array
function exponentialSearch($arr, $n, $x)
{
// If x is present at
// first location itself
if ($arr[0] == $x)
return 0;
// Find range for binary search
// by repeated doubling
$i = 1;
while ($i< $n and $arr[$i] <=$x)
$i = $i * 2;
// Call binary search
// for the found range.
return binarySearch($arr, $i / 2,
min($i, $n - 1), $x);
}
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
function binarySearch($arr, $l,
$r, $x)
{
if ($r >= $l)
{
$mid = $l + ($r - $l)/2;
// If the element is
// present at the middle
// itself
if ($arr[$mid] == $x)
return $mid;
// If element is smaller
// than mid, then it
// can only be present
// n left subarray
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
// Else the element
// can only be present
// in right subarray
return binarySearch($arr, $mid + 1,
$r, $x);
}
// We reach here when
// element is not present
// in array
return -1;
}
// Driver code
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = exponentialSearch($arr, $n, $x);
if($result == -1)
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
// This code is contributed by anuj_67
?>
Javascript
<script>
// Javascript program to find an element x
// in a sorted array using Exponential Search
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
function binarySearch(arr, l, r, x)
{
if (r >= l)
{
let mid = l + (r - l) / 2;
// If the element is present
// at the middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than
// mid, then it can only be
// present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only
// be present in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element
// is not present in array
return -1;
}
// Returns position of first
// occurrence of x in array
function exponentialSearch(arr, n, x)
{
// If x is present at
// first location itself
if (arr[0] == x)
return 0;
// Find range for binary search
// by repeated doubling
let i = 1;
while (i < n && arr[i] <= x)
i = i * 2;
// Call binary search for
// the found range.
return binarySearch(arr, i/2,
Math.min(i, n - 1), x);
}
// Driver Code
let arr = [2, 3, 4, 10, 40];
let n = arr.length;
let x = 10;
let result = exponentialSearch(arr, n, x);
if (result == -1)
document.write("Element is not present in array");
else
document.write("Element is present at index " + result);
</script>
Producción
Element is present at index 3
Complejidad de tiempo: O(Log n)
Espacio auxiliar: La implementación anterior de la búsqueda binaria es recursiva y requiere espacio O(Log n). Con la búsqueda binaria iterativa, solo necesitamos espacio O(1).
Aplicaciones de la Búsqueda Exponencial:
- La búsqueda binaria exponencial es particularmente útil para búsquedas ilimitadas, donde el tamaño de la array es infinito. Consulte Búsqueda binaria ilimitada para ver un ejemplo.
- Funciona mejor que la búsqueda binaria para arrays acotadas, y también cuando el elemento a buscar está más cerca del primer elemento.
Referencia:
https://en.wikipedia.org/wiki/Exponential_search
Echa un vistazo al curso de autoaprendizaje de DSA
Este artículo es una contribución de Pankaj Sharma . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo 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.
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