Búsqueda binaria en Java interactiva y recursiva
- Algoritmo de búsqueda binaria iterativa
- Programa iterativo Java para búsqueda binaria
- Algoritmo de búsqueda binaria recursiva
- Programa recursivo de Java para búsqueda binaria
-
Arrays.binarySearch()
Descripción general - Programa Java para búsqueda binaria
Algoritmo de búsqueda binaria iterativa
Supongamos que tenemos un array sin clasificar A[]
que contiene n
elementos, y queremos encontrar un elemento X
.
-
Establece
lo
como0
yhi
comon - 1
. -
Mientras que
lo
<hi
:- Ajuste
mid
=lo + (hi - lo)/2
. - Si
A[mid] == X
, hemos encontrado que el elemento devuelve el índicemid
. - Si
A[mid] < X
, descarte la mitad izquierda de los elementos y establezcalo
comomid+1
. - De lo contrario, si
A[mid] > X
, descarte la mitad derecha de los elementos y establezcahi
comomid-1
.
- Ajuste
-
El elemento no se encuentra, así que devuelve
-1
.
Programa iterativo Java para búsqueda binaria
class BinarySearch {
int binarySearch(int arr[], int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] < x)
lo = mid + 1;
else
hi = mid - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int x = 5;
int position = ob.binarySearch(arr, x);
if (position == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index: " + position);
}
}
Producción :
Element found at index: 4
Algoritmo de búsqueda binaria recursiva
Supongamos que tenemos un array sin clasificar A[]
que contiene n
elementos, y queremos encontrar un elemento X
.
-
Inicializar
lo
como0
yhi
comon-1
. -
si
lo
>hi
, hemos agotado el espacio de búsqueda del array, devuelve -1. -
Calcula el punto medio
mid
comolo+(hi-lo)/2
. Dividel array en dos partes: la mitad inferior con elementos de0
amid - 1
, y la mitad superior con elementos demid
an - 1
. -
Si
X
==mid
, hemos encontrado que el elemento de destino devuelvemid
. -
Si
X
es menor quemid
, busca en la mitad inferior del array llamando de forma recursiva abinarysearch(arr, lo, mid-1)
. -
De lo contrario, si
X
es mayor quemid
, busque en la mitad superior del array llamando de forma recursiva abinarysearch(arr, mid+1, hi)
.
Programa recursivo de Java para búsqueda binaria
class BinarySearch {
int binarySearch(int arr[], int lo, int hi, int x) {
if (hi >= lo && lo < arr.length - 1) {
int mid = lo + (hi - lo) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, lo, mid - 1, x);
return binarySearch(arr, mid + 1, hi, x);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {1, 2, 3, 4, 5};
int n = arr.length;
int x = 2;
int position = ob.binarySearch(arr, 0, n - 1, x);
if (position == -1)
System.out.println("Element not found !!!");
else
System.out.println("Element found at index: " + position);
}
}
Producción :
Element found at index: 1
Arrays.binarySearch()
Descripción general
Java nos proporciona una función lista para usar Arrays.binarySearch()
para que no tengamos que implementar la función nosotros mismos. Es un método muy simple de usar, implementado eficientemente y no es propenso a errores.
Sintaxis
public static int binarySearch(T arr, T key)
T
puede ser cualquiera de los siguientes: int
, float
, short
, long
, byte
, char
, double
, e incluso un Object
definido por el usuario.
Al igual que nuestra búsqueda binaria implementada, también requiere que el array se ordene; de lo contrario, los resultados no estarán definidos. Busca en el array usando el algoritmo de búsqueda binaria y encuentra el índice del elemento objetivo. Si hay varias apariciones del elemento de destino, puede devolver el índice de cualquiera de ellos.
Parámetros
Arr |
el array de entrada |
Key |
El elemento de destino que estamos buscando. |
Retorna
Si encuentra el elemento de destino, devuelve su índice. De lo contrario, devuelve beg - 1
donde beg
es el índice inicial del espacio de búsqueda del array.
Programa Java para búsqueda binaria
import java.util.Arrays;
class BinarySearchExample {
public static void main(String args[]) {
int arr[] = {1, 2, 3, 4, 5};
int key = 2;
int result = Arrays.binarySearch(arr, key);
if (result < 0)
System.out.println("Element is not found!");
else
System.out.println("Element is found at index: " + result);
}
}
Producción :
Element is found at index: 1
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn