La búsqueda ternaria es un algoritmo de disminución (por constante) y conquista que se puede usar para encontrar un elemento en una array . Es similar a la búsqueda binaria donde dividimos la array en dos partes, pero en este algoritmo, dividimos la array dada en tres partes y determinamos cuál tiene la clave (elemento buscado). Podemos dividir la array en tres partes tomando mid1 y mid2, que se pueden calcular como se muestra a continuación. Inicialmente, l y r serán iguales a 0 y n-1 respectivamente, donde n es la longitud de la array.
Es lo mismo que la búsqueda binaria. La única diferencia es que reduce un poco más la complejidad del tiempo. Su complejidad temporal es O(log n base 3) y la de búsqueda binaria es O(log n base 2).
mid1 = l + (rl)/3
mid2 = r – (rl)/3
Nota: la array debe ordenarse para realizar una búsqueda ternaria en ella.
Pasos para realizar la búsqueda ternaria:
- Primero, comparamos la clave con el elemento en mid1. Si se encuentra igual, devolvemos mid1.
- Si no, comparamos la clave con el elemento en mid2. Si se encuentra igual, devolvemos mid2.
- De lo contrario, verificamos si la clave es menor que el elemento en mid1. En caso afirmativo, recurra a la primera parte.
- De lo contrario, verificamos si la clave es mayor que el elemento en mid2. En caso afirmativo, recurra a la tercera parte.
- Si no, recurrimos a la segunda parte (media).
Ejemplo:
Implementación recursiva de búsqueda ternaria
C++
// C++ program to illustrate
// recursive approach to ternary search
#include <bits/stdc++.h>
using namespace std;
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
cout << "Index of " << key
<< " is " << p << endl;
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
cout << "Index of " << key
<< " is " << p << endl;
}
// This code is contributed
// by Akanksha_Rai
C
// C program to illustrate
// recursive approach to ternary search
#include <stdio.h>
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d\n", key, p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d", key, p);
}
Java
// Java program to illustrate
// recursive approach to ternary search
class GFG {
// Function to perform Ternary Search
static int ternarySearch(int l, int r, int key, int ar[])
{
if (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
// Driver code
public static void main(String args[])
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
System.out.println("Index of " + key + " is " + p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
System.out.println("Index of " + key + " is " + p);
}
}
Python3
# Python3 program to illustrate
# recursive approach to ternary search
import math as mt
# Function to perform Ternary Search
def ternarySearch(l, r, key, ar):
if (r >= l):
# Find the mid1 and mid2
mid1 = l + (r - l) //3
mid2 = r - (r - l) //3
# Check if key is present at any mid
if (ar[mid1] == key):
return mid1
if (ar[mid2] == key):
return mid2
# Since key is not present at mid,
# check in which region it is present
# then repeat the Search operation
# in that region
if (key < ar[mid1]):
# The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar)
elif (key > ar[mid2]):
# The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar)
else:
# The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1,
mid2 - 1, key, ar)
# Key not found
return -1
# Driver code
l, r, p = 0, 9, 5
# Get the array
# Sort the array if not sorted
ar = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
# Starting index
l = 0
# length of array
r = 9
# Checking for 5
# Key to be searched in the array
key = 5
# Search the key using ternarySearch
p = ternarySearch(l, r, key, ar)
# Print the result
print("Index of", key, "is", p)
# Checking for 50
# Key to be searched in the array
key = 50
# Search the key using ternarySearch
p = ternarySearch(l, r, key, ar)
# Print the result
print("Index of", key, "is", p)
# This code is contributed by
# Mohit kumar 29
C#
// CSharp program to illustrate
// recursive approach to ternary search
using System;
class GFG {
// Function to perform Ternary Search
static int ternarySearch(int l, int r, int key, int[] ar)
{
if (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
// Driver code
public static void Main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int[] ar = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
Console.WriteLine("Index of " + key + " is " + p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
Console.WriteLine("Index of " + key + " is " + p);
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP program to illustrate
// recursive approach to ternary search
// Function to perform Ternary Search
function ternarySearch($l, $r, $key, $ar)
{
if ($r >= $l)
{
// Find the mid1 and mid2
$mid1 = (int)($l + ($r - $l) / 3);
$mid2 = (int)($r - ($r - $l) / 3);
// Check if key is present at any mid
if ($ar[$mid1] == $key)
{
return $mid1;
}
if ($ar[$mid2] == $key)
{
return $mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if ($key < $ar[$mid1])
{
// The key lies in between l and mid1
return ternarySearch($l, $mid1 - 1,
$key, $ar);
}
else if ($key > $ar[$mid2])
{
// The key lies in between mid2 and r
return ternarySearch($mid2 + 1, $r,
$key, $ar);
}
else
{
// The key lies in between mid1 and mid2
return ternarySearch($mid1 + 1, $mid2 - 1,
$key, $ar);
}
}
// Key not found
return -1;
}
// Driver code
// Get the array
// Sort the array if not sorted
$ar = array( 1, 2, 3, 4, 5,
6, 7, 8, 9, 10 );
// Starting index
$l = 0;
// length of array
$r = 9;
// Checking for 5
// Key to be searched in the array
$key = 5;
// Search the key using ternarySearch
$p = ternarySearch($l, $r, $key, $ar);
// Print the result
echo "Index of ", $key,
" is ", (int)$p, "\n";
// Checking for 50
// Key to be searched in the array
$key = 50;
// Search the key using ternarySearch
$p = ternarySearch($l, $r, $key, $ar);
// Print the result
echo "Index of ", $key,
" is ", (int)$p, "\n";
// This code is contributed by Arnab Kundu
?>
Javascript
<script>
// JavaScript program to illustrate
// recursive approach to ternary search
// Function to perform Ternary Search
function ternarySearch(l, r, key, ar)
{
if (r >= l) {
// Find the mid1 and mid2
let mid1 = l + parseInt((r - l) / 3, 10);
let mid2 = r - parseInt((r - l) / 3, 10);
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
return ternarySearch(l, mid1 - 1, key, ar);
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
return ternarySearch(mid2 + 1, r, key, ar);
}
else {
// The key lies in between mid1 and mid2
return ternarySearch(mid1 + 1, mid2 - 1, key, ar);
}
}
// Key not found
return -1;
}
let l, r, p, key;
// Get the array
// Sort the array if not sorted
let ar = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
document.write("Index of " + key + " is " + p + "</br>");
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
document.write("Index of " + key + " is " + p);
</script>
Producción:
Index of 5 is 4 Index of 50 is -1
Complejidad de tiempo: O (log 3 n)
Espacio Auxiliar: O(log 3 n)
Enfoque iterativo de búsqueda ternaria
C++
// C++ program to illustrate
// iterative approach to ternary search
#include <iostream>
using namespace std;
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
while (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
r = mid1 - 1;
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
l = mid2 + 1;
}
else {
// The key lies in between mid1 and mid2
l = mid1 + 1;
r = mid2 - 1;
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
cout << "Index of "<<key<<" is " << p << endl;
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
cout << "Index of "<<key<<" is " << p;
}
C
// C program to illustrate
// iterative approach to ternary search
#include <stdio.h>
// Function to perform Ternary Search
int ternarySearch(int l, int r, int key, int ar[])
{
while (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
r = mid1 - 1;
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
l = mid2 + 1;
}
else {
// The key lies in between mid1 and mid2
l = mid1 + 1;
r = mid2 - 1;
}
}
// Key not found
return -1;
}
// Driver code
int main()
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d\n", key, p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
printf("Index of %d is %d", key, p);
}
Java
// Java program to illustrate
// the iterative approach to ternary search
class GFG {
// Function to perform Ternary Search
static int ternarySearch(int l, int r, int key, int ar[])
{
while (r >= l) {
// Find the mid1 mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
r = mid1 - 1;
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
l = mid2 + 1;
}
else {
// The key lies in between mid1 and mid2
l = mid1 + 1;
r = mid2 - 1;
}
}
// Key not found
return -1;
}
// Driver code
public static void main(String args[])
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int ar[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
System.out.println("Index of " + key + " is " + p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
System.out.println("Index of " + key + " is " + p);
}
}
Python3
# Python 3 program to illustrate iterative
# approach to ternary search
# Function to perform Ternary Search
def ternarySearch(l, r, key, ar):
while r >= l:
# Find mid1 and mid2
mid1 = l + (r-l) // 3
mid2 = r - (r-l) // 3
# Check if key is at any mid
if key == ar[mid1]:
return mid1
if key == mid2:
return mid2
# Since key is not present at mid,
# Check in which region it is present
# Then repeat the search operation in that region
if key < ar[mid1]:
# key lies between l and mid1
r = mid1 - 1
elif key > ar[mid2]:
# key lies between mid2 and r
l = mid2 + 1
else:
# key lies between mid1 and mid2
l = mid1 + 1
r = mid2 - 1
# key not found
return -1
# Driver code
# Get the list
# Sort the list if not sorted
ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Starting index
l = 0
# Length of list
r = 9
# Checking for 5
# Key to be searched in the list
key = 5
# Search the key using ternary search
p = ternarySearch(l, r, key, ar)
# Print the result
print("Index of", key, "is", p)
# Checking for 50
# Key to be searched in the list
key = 50
# Search the key using ternary search
p = ternarySearch(l, r, key, ar)
# Print the result
print("Index of", key, "is", p)
# This code has been contributed by Sujal Motagi
C#
// C# program to illustrate the iterative
// approach to ternary search
using System;
public class GFG {
// Function to perform Ternary Search
static int ternarySearch(int l, int r,
int key, int[] ar)
{
while (r >= l) {
// Find the mid1 and mid2
int mid1 = l + (r - l) / 3;
int mid2 = r - (r - l) / 3;
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
r = mid1 - 1;
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
l = mid2 + 1;
}
else {
// The key lies in between mid1 and mid2
l = mid1 + 1;
r = mid2 - 1;
}
}
// Key not found
return -1;
}
// Driver code
public static void Main(String[] args)
{
int l, r, p, key;
// Get the array
// Sort the array if not sorted
int[] ar = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
Console.WriteLine("Index of " + key + " is " + p);
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
Console.WriteLine("Index of " + key + " is " + p);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to illustrate the iterative
// approach to ternary search
// Function to perform Ternary Search
function ternarySearch(l, r, key, ar)
{
while (r >= l) {
// Find the mid1 and mid2
let mid1 = l + parseInt((r - l) / 3, 10);
let mid2 = r - parseInt((r - l) / 3, 10);
// Check if key is present at any mid
if (ar[mid1] == key) {
return mid1;
}
if (ar[mid2] == key) {
return mid2;
}
// Since key is not present at mid,
// check in which region it is present
// then repeat the Search operation
// in that region
if (key < ar[mid1]) {
// The key lies in between l and mid1
r = mid1 - 1;
}
else if (key > ar[mid2]) {
// The key lies in between mid2 and r
l = mid2 + 1;
}
else {
// The key lies in between mid1 and mid2
l = mid1 + 1;
r = mid2 - 1;
}
}
// Key not found
return -1;
}
let l, r, p, key;
// Get the array
// Sort the array if not sorted
let ar = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
// Starting index
l = 0;
// length of array
r = 9;
// Checking for 5
// Key to be searched in the array
key = 5;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
document.write("Index of " + key + " is " + p + "</br>");
// Checking for 50
// Key to be searched in the array
key = 50;
// Search the key using ternarySearch
p = ternarySearch(l, r, key, ar);
// Print the result
document.write("Index of " + key + " is " + p);
</script>
Producción:
Index of 5 is 4 Index of 50 is -1
Complejidad de tiempo: O (log 3 n), donde n es el tamaño de la array.
Espacio Auxiliar: O(1)
Búsqueda binaria Vs Búsqueda ternaria
La complejidad temporal de la búsqueda binaria es mayor que la búsqueda ternaria, pero eso no significa que la búsqueda ternaria sea mejor. En realidad, la cantidad de comparaciones en la búsqueda ternaria es mucho mayor, lo que la hace más lenta que la búsqueda binaria.
Usos: Para encontrar el máximo o mínimo de una función unimodal .
Problemas de Hackerearth en la búsqueda ternaria