Los algoritmos de búsqueda están diseñados para verificar un elemento o recuperar un elemento de cualquier estructura de datos donde esté almacenado. Principalmente los algoritmos de búsqueda más utilizados son:
Búsqueda lineal: en esta, la lista o array se recorre secuencialmente y se verifica cada elemento. Y la búsqueda lineal se puede implementar en arrays o listas ordenadas y no ordenadas. La búsqueda lineal tiene una complejidad de tiempo lineal, es decir, O (N)
Búsqueda binaria: es un algoritmo de búsqueda diseñado específicamente para buscar en estructuras de datos ordenados . Este algoritmo de búsqueda es mucho más eficiente que la búsqueda lineal , ya que apuntan repetidamente al centro de la estructura de búsqueda y dividen el espacio de búsqueda por la mitad. Tiene una complejidad de tiempo logarítmica, es decir, O (log N) .
Ahora, surge la pregunta, ¿ la búsqueda binaria es aplicable en arrays no ordenadas?
Entonces, la respuesta es NO , no es posible usar o implementar la búsqueda binaria en arrays o listas no ordenadas, porque la orientación repetida del elemento medio de una mitad depende del orden ordenado de la estructura de datos.
Solución alternativa para aplicar la búsqueda binaria en una array sin ordenar:
Sin embargo, si es necesario hacerlo explícitamente, entonces:
Construya una array auxiliar de pares de elementos con sus índices y simplemente ordene la array y realice una búsqueda binaria para X dada en la array auxiliar ordenada
Siga los pasos a continuación:
- Para cada elemento de la array, escriba los elementos y sus índices en una array auxiliar de pares.
- Ordenar array auxiliar.
- Para el valor dado X, realice una búsqueda binaria en la array auxiliar ordenada,
- Deje que la posición sea el índice donde el elemento X está en la array auxiliar.
- Retorna el índice del elemento en la array original arr(aux_array[posición].segundo).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach:
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > aux_arr;
// Function to make auxiliary array
void make_aux_array(int arr[], int n)
{
aux_arr.resize(n);
// For every element in array write
// elements and their indices in
// auxiliary array of pairs.
for (int i = 0; i < n; i++) {
aux_arr[i] = { arr[i], i };
}
// Sort auxiliary array.
sort(aux_arr.begin(), aux_arr.end());
}
// Function to perform binary search
int binarySearch(int arr[], int n, int x)
{
// For given value x perform
// Binary Search on sorted auxiliary
// array, let position be the index
// where element x is in
// auxiliary array.
int position
= lower_bound(aux_arr.begin(),
aux_arr.end(),
make_pair(x, 0))
- aux_arr.begin();
if (position < n
&& aux_arr[position].first == x) {
// Return index of element in
// original array arr
// (aux_array[position].second).
return aux_arr[position].second;
}
else {
return -1;
}
}
// Print Function
void print(int arr[], int n, int x)
{
make_aux_array(arr, n);
int result = binarySearch(arr, n, x);
if (result == -1) {
cout << -1 << endl;
}
else {
cout << result << endl;
}
}
// Driver code
int main()
{
int arr[] = { 15, 12, 13, 19, 11,
10, 18, 17, 14, 16 };
int N = sizeof(arr) / sizeof(arr[0]);
int X = 18;
// Function call
print(arr, N, X);
return 0;
}
C
// C program to implement above approach
#include <stdio.h>
#include <stdlib.h>
// Structure to make a pair
typedef struct {
int value, index;
} pair;
// Function to compare pairs
int cmp_pair(const void* a, const void* b)
{
return ((*(pair*)a).value
- (*(pair*)b).value);
}
pair* aux_arr;
// Function to make auxiliary array
void make_aux_array(int arr[], int n)
{
aux_arr = (pair*)malloc(n * sizeof(pair));
// For every element in array
// write elements and
// their indices in auxiliary array
for (int i = 0; i < n; i++) {
aux_arr[i].value = arr[i];
aux_arr[i].index = i;
}
// Sort auxiliary array.
qsort(aux_arr, n, sizeof(pair),
cmp_pair);
}
// Function to implement binary search
int binarySearch(int arr[], int n, int x)
{
// For given value x perform Binary Search
// on sorted auxiliary array.
// Let position be the index where
// element x is in auxiliary array.
pair key = { x, 0 };
pair* found = (pair*)bsearch(
&key, aux_arr, n, sizeof(pair), cmp_pair);
if (found != NULL) {
int position = found - aux_arr;
// Return index of element
// in original array arr
// (aux_array[position].second).
return aux_arr[position].index;
}
else {
return -1;
}
}
// Driver code
int main()
{
int arr[] = { 15, 12, 13, 19, 11,
10, 18, 17, 14, 16 };
int x = 18;
int n = sizeof(arr) / sizeof(arr[0]);
make_aux_array(arr, n);
// Function call
int result = binarySearch(arr, n, x);
printf("%d\n", result);
return 0;
}
Java
// Java program for the above approach:
import java.util.*;
// User defined Pair class
class Pair {
int first;
int second;
// Constructor
public Pair(int x, int y)
{
this.first = x;
this.second = y;
}
}
class GFG {
static ArrayList<Pair> aux_arr;
// Function to make auxiliary array
static void make_aux_array(int arr[], int n)
{
aux_arr = new ArrayList<Pair>();
// For every element in array write
// elements and their indices in
// auxiliary array of pairs.
for (int i = 0; i < n; i++) {
aux_arr.add(new Pair(arr[i], i));
}
// Sort auxiliary array in non increasing
// order
aux_arr.sort((a, b) -> (-a.first + b.first));
}
// Function to perform binary search
static int binarySearch(int arr[], int n, int x)
{
// For given value x perform
// Binary Search on sorted auxiliary
// array, let position be the index
// where element x is in
// auxiliary array.
int position = aux_arr.size() - 1;
for (int i = 0; i < aux_arr.size(); i++) {
Pair elem = aux_arr.get(i);
if (elem.first >= x && elem.second >= 0)
position = i;
}
if (position < n
&& aux_arr.get(position).first == x) {
// Return index of element in
// original array arr
// (aux_array[position].second).
return aux_arr.get(position).second;
}
else {
return -1;
}
}
// Print Function
static void print(int arr[], int n, int x)
{
make_aux_array(arr, n);
int result = binarySearch(arr, n, x);
if (result == -1) {
System.out.println(-1);
}
else {
System.out.println(result);
}
}
// Driver code
public static void main(String[] args)
{
int[] arr
= { 15, 12, 13, 19, 11, 10, 18, 17, 14, 16 };
int N = arr.length;
int X = 18;
// Function call
print(arr, N, X);
}
}
// This code is contributed by phasing17
Python3
# Python3 program for the above approach aux_arr = [] # Function to make auxiliary array def make_aux_array(arr, n): global aux_arr # For every element in array write # elements and their indices in # auxiliary array of pairs for i in range(n): aux_arr.append([arr[i], i]) # sort auxiliary array aux_arr.sort() # Function to perform binary search def binarySearch(arr, n, x): global aux_arr # For given value x perform # Binary Search on sorted auxiliary # array, let position be the index # where element x or the element # just greater than x # is in auxiliary array position = n for i in range(n): if aux_arr[i][0] == x: position = i # return index of element in # original array arr # aux_array[position][1] return aux_arr[position][1] return -1 # print function def printFunc(arr, n, x): global aux_arr make_aux_array(arr, n) result = binarySearch(arr, n, x) if result == -1: print(-1) else: print(result) # Driver Code arr = [15, 12, 13, 19, 11, 10, 18, 17, 14, 16] N = len(arr) X = 18 # Function call printFunc(arr, N, X) # This code is contributed by phasing17.
Javascript
// JavaScript program for the above approach
let aux_arr = [];
// Function to make auxiliary array
function make_aux_array(arr, n)
{
// For every element in array write
// elements and their indices in
// auxiliary array of pairs
for (let i = 0; i < n; i++) {
aux_arr.push([arr[i], i]);
}
// sort auxiliary array
aux_arr.sort();
}
// Function to perform binary search
function binarySearch(arr, n, x) {
// For given value x perform
// Binary Search on sorted auxiliary
// array, let position be the index
// where element x or the element
// just greater than x
// is in auxiliary array
let position = n;
for (let i = 0; i <= n; i++) {
if (aux_arr[i][0] == x) {
position = i;
// return index of element in
// original array arr
// aux_array[position][1]
return aux_arr[position][1];
}
}
return -1;
}
// print function
function print(arr, n, x) {
make_aux_array(arr, n);
let result = binarySearch(arr, n, x);
if (result == -1) console.log(-1);
else console.log(result);
}
// Driver Code
let arr = [15, 12, 13, 19, 11, 10, 18, 17, 14, 16];
let n = arr.length;
let x = 18;
// Function call
print(arr, n, x);
// This code is contributed by Ishan Khandelwal.
6
Complejidad del tiempo: O(N*log N)
- Clasificación de array auxiliar O(N* log N)
- Búsqueda binaria O (registro N)
Espacio Auxiliar: O(N)
Conclusión: se puede ver a partir de la solución alternativa que usar la búsqueda binaria toma más tiempo en comparación con la búsqueda lineal y también usa espacio adicional. Por lo tanto, no se recomienda utilizar la búsqueda binaria para una array sin ordenar.
Publicación traducida automáticamente
Artículo escrito por zlatkodamijanic y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA