La siguiente es una función de búsqueda binaria recursiva simple en C++ tomada de aquí .
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// 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
// in 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;
}
// This code is contributed by sanjoy_62.
C
// 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
// in 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;
}
Java
// 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
// in 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;
}
// This code is contributed by gauravrajput1
Python3
# A recursive binary search function. It 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 element is smaller than mid, then it can only be present # in 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; # This code is contributed by umadevi9616
C#
// 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
// in 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;
}
// This code is contributed by gauravrajput1
Javascript
<script>
// 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)
{
var 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
// in 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;
}
// This code is contributed by gauravrajput1
</script>
La siguiente es una función de búsqueda ternaria recursiva simple :
C
// A recursive ternary search function. It returns location of x in
// given array arr[l..r] is present, otherwise -1
int ternarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l)/3;
int mid2 = mid1 + (r - l)/3;
// If x is present at the mid1
if (arr[mid1] == x) return mid1;
// If x is present at the mid2
if (arr[mid2] == x) return mid2;
// If x is present in left one-third
if (arr[mid1] > x) return ternarySearch(arr, l, mid1-1, x);
// If x is present in right one-third
if (arr[mid2] < x) return ternarySearch(arr, mid2+1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1+1, mid2-1, x);
}
// We reach here when element is not present in array
return -1;
}
Java
import java.io.*;
class GFG
{
public static void main (String[] args)
{
// A recursive ternary search function.
// It returns location of x in given array
// arr[l..r] is present, otherwise -1
static int ternarySearch(int arr[], int l,
int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l) / 3;
int mid2 = mid1 + (r - l) / 3;
// If x is present at the mid1
if (arr[mid1] == x) return mid1;
// If x is present at the mid2
if (arr[mid2] == x) return mid2;
// If x is present in left one-third
if (arr[mid1] > x)
return ternarySearch(arr, l, mid1 - 1, x);
// If x is present in right one-third
if (arr[mid2] < x)
return ternarySearch(arr, mid2 + 1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1 + 1,
mid2 - 1, x);
}
// We reach here when element is
// not present in array
return -1;
}
}
Python3
# A recursive ternary search function. It returns location of x in # given array arr[l..r] is present, otherwise -1 def ternarySearch(arr, l, r, x): if (r >= l): mid1 = l + (r - l)//3 mid2 = mid1 + (r - l)//3 # If x is present at the mid1 if arr[mid1] == x: return mid1 # If x is present at the mid2 if arr[mid2] == x: return mid2 # If x is present in left one-third if arr[mid1] > x: return ternarySearch(arr, l, mid1-1, x) # If x is present in right one-third if arr[mid2] < x: return ternarySearch(arr, mid2+1, r, x) # If x is present in middle one-third return ternarySearch(arr, mid1+1, mid2-1, x) # We reach here when element is not present in array return -1 # This code is contributed by ankush_953
C#
// A recursive ternary search function.
// It returns location of x in given array
// arr[l..r] is present, otherwise -1
static int ternarySearch(int []arr, int l,
int r, int x)
{
if (r >= l)
{
int mid1 = l + (r - l) / 3;
int mid2 = mid1 + (r - l) / 3;
// If x is present at the mid1
if (arr[mid1] == x) return mid1;
// If x is present at the mid2
if (arr[mid2] == x) return mid2;
// If x is present in left one-third
if (arr[mid1] > x)
return ternarySearch(arr, l, mid1 - 1, x);
// If x is present in right one-third
if (arr[mid2] < x)
return ternarySearch(arr, mid2 + 1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1 + 1,
mid2 - 1, x);
}
// We reach here when element is
// not present in array
return -1;
}
// This code is contributed by gauravrajput1
PHP
<?php
// A recursive ternary search function.
// It returns location of x in
// given array arr[l..r] is
// present, otherwise -1
function ternarySearch($arr, $l,
$r, $x)
{
if ($r >= $l)
{
$mid1 = $l + ($r - $l) / 3;
$mid2 = $mid1 + ($r - l) / 3;
// If x is present at the mid1
if ($arr[mid1] == $x)
return $mid1;
// If x is present
// at the mid2
if ($arr[$mid2] == $x)
return $mid2;
// If x is present in
// left one-third
if ($arr[$mid1] > $x)
return ternarySearch($arr, $l,
$mid1 - 1, $x);
// If x is present in right one-third
if ($arr[$mid2] < $x)
return ternarySearch($arr, $mid2 + 1,
$r, $x);
// If x is present in
// middle one-third
return ternarySearch($arr, $mid1 + 1,
$mid2 - 1, $x);
}
// We reach here when element
// is not present in array
return -1;
}
// This code is contributed by anuj_67
?>
Javascript
<script>
// A recursive ternary search function.
// It returns location of x in given array
// arr[l..r] is present, otherwise -1
function ternarySearch(arr , l , r , x) {
if (r >= l) {
var mid1 = l + parseInt((r - l) / 3);
var mid2 = mid1 + parseInt((r - l) / 3);
// If x is present at the mid1
if (arr[mid1] == x)
return mid1;
// If x is present at the mid2
if (arr[mid2] == x)
return mid2;
// If x is present in left one-third
if (arr[mid1] > x)
return ternarySearch(arr, l, mid1 - 1, x);
// If x is present in right one-third
if (arr[mid2] < x)
return ternarySearch(arr, mid2 + 1, r, x);
// If x is present in middle one-third
return ternarySearch(arr, mid1 + 1, mid2 - 1, x);
}
// We reach here when element is
// not present in array
return -1;
// This code is contributed by gauravrajput1
</script>
¿Cuál de los dos anteriores hace menos comparaciones en el peor de los casos?
A primera vista, parece que la búsqueda ternaria hace menos comparaciones, ya que hace llamadas recursivas Log 3 n, pero la búsqueda binaria hace llamadas recursivas Log 2 n. Echemos un vistazo más de cerca.
La siguiente es una fórmula recursiva para contar comparaciones en el peor de los casos de búsqueda binaria.
T(n) = T(n/2) + 2, T(1) = 1
La siguiente es una fórmula recursiva para contar comparaciones en el peor de los casos de búsqueda ternaria.
T(n) = T(n/3) + 4, T(1) = 1
En la búsqueda binaria, hay comparaciones 2Log 2 n + 1 en el peor de los casos. En la búsqueda ternaria, hay 4Log 3 n + 1 comparaciones en el peor de los casos.
Time Complexity for Binary search = 2clog2n + O(1) Time Complexity for Ternary search = 4clog3n + O(1)
Por lo tanto, la comparación de búsquedas ternarias y binarias se reduce a la comparación de las expresiones 2Log 3 n y Log 2 n . El valor de 2Log 3 n se puede escribir como (2 / Log 2 3) * Log 2 n . Dado que el valor de (2 / Log 2 3) es más de uno, la búsqueda ternaria realiza más comparaciones que la búsqueda binaria en el peor de los casos.
Ejercicio:
¿Por qué Merge Sort divide la array de entrada en dos mitades, por qué no en tres o más partes?
Este artículo es una contribución de Anmol . 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