Order-Agnostic Binary Search es una versión modificada del algoritmo Binary Search . Aquí, en esta búsqueda binaria modificada, viene con una verificación de condición más. La intuición detrás de este algoritmo es qué pasa si no se da el orden de la array ordenada. Entonces aquí verifique que el valor del primer elemento sea mayor o menor que el último elemento.
- Si el primer elemento es más pequeño que el último elemento, entonces si el valor de la clave de búsqueda X es menor que la mitad del intervalo, el puntero final se cambiará a la mitad -1; de lo contrario, el inicio se cambiará a la mitad + 1.
- Si el primer elemento es mayor que el último elemento , entonces si el valor de la clave de búsqueda X es menor que la mitad del intervalo, el puntero de inicio se moverá al siguiente elemento del elemento medio; de lo contrario, el puntero final se moverá anterior a la mitad elemento.
Al final, si el valor de la clave de búsqueda coincide con el elemento central, se encuentra el elemento que se proporcionó a la búsqueda.
Implementación de búsqueda binaria agnóstica de orden:
Veamos la implementación de Order-Agnostic Binary Search con la ayuda de un ejemplo.
Dada una array , arr[ ] de tamaño N y un elemento X y la array está ordenada en cualquier orden (ascendente o descendente), la tarea es encontrar si el elemento x está presente en la array o no. En caso afirmativo, imprima su índice, de lo contrario, imprima -1.
Ejemplos:
Entrada: arr[] = {40, 10, 5, 2, 1}, N=5, X=10
Salida: 1
Explicación:
La array se ordena en orden descendente y el elemento está presente en el índice 1.
Entrada: arr[] = {1}, N=1, X=10
Salida: -1
Enfoque: la idea de fuerza bruta sería atravesar linealmente la array y verificar si el elemento está presente en la array o no. La optimización de este algoritmo sería utilizar la búsqueda binaria si se conociera el orden de clasificación de la array: ascendente/descendente. Se puede utilizar una variación de la búsqueda binaria, es decir, la búsqueda binaria agnóstica del pedido, como se indica a continuación:
Siga los pasos a continuación para resolver el problema utilizando la búsqueda binaria agnóstica de pedidos:
- Inicialice una variable booleana isAsc como verdadera si arr[inicio] es menor que arr[fin]; de lo contrario, configúrela como falsa.
- Atraviese un ciclo while hasta que el inicio sea menor que el final y realice los siguientes pasos:
- Inicialice la variable medio como el promedio de inicio y final.
- Si arr[medio] es igual a X, devuelva el valor de medio como respuesta,
- Si la array está en orden ascendente, realice los siguientes pasos:
- Si arr[medio] es menor que X, establezca el valor de inicio como medio+1 ; de lo contrario, establezca el valor de fin como medio-1.
- De lo contrario, si arr[medio] es menor que X, establezca el valor de fin como medio-1; de lo contrario, establezca el valor de inicio como medio+1.
- Después de realizar los pasos anteriores, devuelva el valor de -1 como respuesta ya que no se encuentra el elemento.
Implementación iterativa de Order-Agnostic Binary Search .
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// An iterative binary search function.
int binarySearch(int arr[], int start, int end, int x)
{
// Checking the sorted order of the given array
bool isAsc = arr[start] < arr[end];
while (start <= end) {
int middle = start + (end - start) / 2;
// Check if x is present at mid
if (arr[middle] == x)
return middle;
// Ascending order
if (isAsc == true) {
// If x greater, ignore left half
if (arr[middle] < x)
start = middle + 1;
// If x smaller, ignore right half
else
end = middle - 1;
}
// Descending order
else {
// If x smaller, ignore left half
if (arr[middle] > x)
start = middle + 1;
// If x greater, ignore right half
else
end = middle - 1;
}
}
// Element is not present
return -1;
}
// Driver Code
int main()
{
int arr[] = { 40, 10, 5, 2, 1 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
cout << binarySearch(arr, 0, n - 1, x);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// An iterative binary search function.
static int binarySearch(int arr[], int start, int end, int x)
{
// Checking the sorted order of the given array
boolean isAsc = arr[start] < arr[end];
while (start <= end) {
int middle = start + (end - start) / 2;
// Check if x is present at mid
if (arr[middle] == x)
return middle;
// Ascending order
if (isAsc == true) {
// If x greater, ignore left half
if (arr[middle] < x)
start = middle + 1;
// If x smaller, ignore right half
else
end = middle - 1;
}
// Descending order
else {
// If x smaller, ignore left half
if (arr[middle] > x)
start = middle + 1;
// If x greater, ignore right half
else
end = middle - 1;
}
}
// Element is not present
return -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 40, 10, 5, 2, 1 };
int x = 10;
int n = arr.length;
System.out.println(binarySearch(arr, 0, n - 1, x));
}
}
// This code is contributed by sanjoy_62.
Python
# Python program for the above approach # An iterative binary search function. def binarySearch(arr, start, end, x): # Checking the sorted order of the given array isAsc = arr[start] < arr[end] while (start <= end): middle = start + (end - start) // 2 # Check if x is present at mid if (arr[middle] == x): return middle # Ascending order if (isAsc == True): # If x greater, ignore left half if (arr[middle] < x): start = middle + 1 # If x smaller, ignore right half else: end = middle - 1 # Descending order else: # If x smaller, ignore left half if (arr[middle] > x): start = middle + 1 # If x greater, ignore right half else: end = middle - 1 # Element is not present return -1 # Driver Code arr = [ 40, 10, 5, 2, 1 ] x = 10 n = len(arr) print(binarySearch(arr, 0, n - 1, x)) # This code is ciontributed by Samim Hossain Mondal.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// An iterative binary search function.
static int binarySearch(int[] arr, int start, int end, int x)
{
// Checking the sorted order of the given array
bool isAsc = arr[start] < arr[end];
while (start <= end) {
int middle = start + (end - start) / 2;
// Check if x is present at mid
if (arr[middle] == x)
return middle;
// Ascending order
if (isAsc == true) {
// If x greater, ignore left half
if (arr[middle] < x)
start = middle + 1;
// If x smaller, ignore right half
else
end = middle - 1;
}
// Descending order
else {
// If x smaller, ignore left half
if (arr[middle] > x)
start = middle + 1;
// If x greater, ignore right half
else
end = middle - 1;
}
}
// Element is not present
return -1;
}
// Driver Code
public static void Main(String[] args) {
int[] arr = { 40, 10, 5, 2, 1 };
int x = 10;
int n = arr.Length;
Console.Write(binarySearch(arr, 0, n - 1, x));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// An iterative binary search function.
function binarySearch(arr, start, end, x) {
// Checking the sorted order of the given array
let isAsc = arr[start] < arr[end];
while (start <= end) {
let middle = start + Math.floor((end - start) / 2);
// Check if x is present at mid
if (arr[middle] == x)
return middle;
// Ascending order
if (isAsc == true) {
// If x greater, ignore left half
if (arr[middle] < x)
start = middle + 1;
// If x smaller, ignore right half
else
end = middle - 1;
}
// Descending order
else {
// If x smaller, ignore left half
if (arr[middle] > x)
start = middle + 1;
// If x greater, ignore right half
else
end = middle - 1;
}
}
// Element is not present
return -1;
}
// Driver Code
let arr = [40, 10, 5, 2, 1];
let x = 10;
let n = arr.length;
document.write(binarySearch(arr, 0, n - 1, x));
// This code is contributed by Potta Lokesh
</script>
Producción:
1
Complejidad temporal: O(log(N)).
Espacio Auxiliar: O(1)
Implementación recursiva de Order-Agnostic Binary Search:
C++
// C++ 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 start,
int end, int x)
{
bool isAsc = arr[start] < arr[end];
if (end >= start) {
int middle = start + (end - start) / 2;
// If the element is present
// at the middle itself
if (arr[middle] == x)
return middle;
if (isAsc == true) {
// If element is smaller than mid,
// then it can only be
// present in left subarray
if (arr[middle] > x)
return binarySearch(
arr, start,
middle - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, middle + 1,
end, x);
}
else {
if (arr[middle] < x)
return binarySearch(arr, start,
middle - 1, x);
// Else the element can only be present
// in left subarray
return binarySearch(arr, middle + 1,
end, x);
}
}
// Element not found
return -1;
}
// Driver Code
int main(void)
{
int arr[] = { 40, 10, 5, 2, 1 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
cout << binarySearch(arr, 0, n - 1, x);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// 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 start, int end, int x) {
boolean isAsc = arr[start] < arr[end];
if (end >= start) {
int middle = start + (end - start) / 2;
// If the element is present
// at the middle itself
if (arr[middle] == x)
return middle;
if (isAsc == true) {
// If element is smaller than mid,
// then it can only be
// present in left subarray
if (arr[middle] > x)
return binarySearch(arr, start, middle - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, middle + 1, end, x);
} else {
if (arr[middle] < x)
return binarySearch(arr, start, middle - 1, x);
// Else the element can only be present
// in left subarray
return binarySearch(arr, middle + 1, end, x);
}
}
// Element not found
return -1;
}
// Driver Code
public static void main(String[] args) {
int arr[] = { 40, 10, 5, 2, 1 };
int x = 10;
int n = arr.length;
System.out.print(binarySearch(arr, 0, n - 1, x));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python program for the above approach # A recursive binary search function. # It returns location of x in given # array arr[l..r] is present, # otherwise -1 def binarySearch(arr, start, end, x): isAsc = arr[start] < arr[end] if (end >= start): middle = (int)(start + (end - start) / 2) # If the element is present # at the middle itself if (arr[middle] == x): return middle if (isAsc == True): # If element is smaller than mid, # then it can only be # present in left subarray if (arr[middle] > x): return binarySearch( arr, start, middle - 1, x) # Else the element can only be present # in right subarray return binarySearch(arr, middle + 1, end, x) else: if (arr[middle] < x): return binarySearch(arr, start, middle - 1, x) # Else the element can only be present # in left subarray return binarySearch(arr, middle + 1, end, x) # Element not found return -1 # Driver Code arr = [40, 10, 5, 2, 1] x = 10 n = len(arr) print(binarySearch(arr, 0, n - 1, x)) # This code is contributed by Taranpreet
C#
// C# program for the above approach
using System;
public class GFG {
// 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 start, int end, int x) {
bool isAsc = arr[start] < arr[end];
if (end >= start) {
int middle = start + (end - start) / 2;
// If the element is present
// at the middle itself
if (arr[middle] == x)
return middle;
if (isAsc == true) {
// If element is smaller than mid,
// then it can only be
// present in left subarray
if (arr[middle] > x)
return binarySearch(arr, start, middle - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, middle + 1, end, x);
} else {
if (arr[middle] < x)
return binarySearch(arr, start, middle - 1, x);
// Else the element can only be present
// in left subarray
return binarySearch(arr, middle + 1, end, x);
}
}
// Element not found
return -1;
}
// Driver Code
public static void Main(String[] args) {
int []arr = { 40, 10, 5, 2, 1 };
int x = 10;
int n = arr.Length;
Console.Write(binarySearch(arr, 0, n - 1, x));
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// javascript program for the above approach
// A recursive binary search function.
// It returns location of x in given
// array arr[l..r] is present,
// otherwise -1
function binarySearch(arr , start , end , x) {
let isAsc = arr[start] < arr[end];
if (end >= start) {
var middle = start + parseInt((end - start) / 2);
// If the element is present
// at the middle itself
if (arr[middle] == x)
return middle;
if (isAsc == true) {
// If element is smaller than mid,
// then it can only be
// present in left subarray
if (arr[middle] > x)
return binarySearch(arr, start, middle - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, middle + 1, end, x);
} else {
if (arr[middle] < x)
return binarySearch(arr, start, middle - 1, x);
// Else the element can only be present
// in left subarray
return binarySearch(arr, middle + 1, end, x);
}
}
// Element not found
return -1;
}
// Driver Code
var arr = [ 40, 10, 5, 2, 1 ];
var x = 10;
var n = arr.length;
document.write(binarySearch(arr, 0, n - 1, x));
// This code is contributed by Rajput-Ji
</script>
Producción:
1
Complejidad temporal: O(log(N)).
Espacio Auxiliar: O(1)