Búsqueda binaria en Java interactiva y recursiva

Harshit Jindal 12 octubre 2023 Java Java Algorithm
  1. Algoritmo de búsqueda binaria iterativa
  2. Programa iterativo Java para búsqueda binaria
  3. Algoritmo de búsqueda binaria recursiva
  4. Programa recursivo de Java para búsqueda binaria
  5. Arrays.binarySearch() Descripción general
  6. Programa Java para búsqueda binaria
Búsqueda binaria en Java interactiva y recursiva
Nota
Si desea comprender la búsqueda binaria en detalle, consulte el artículo algoritmo de 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 como 0 y hi como n - 1.
  • Mientras que lo < hi:
    • Ajuste mid = lo + (hi - lo)/2.
    • Si A[mid] == X, hemos encontrado que el elemento devuelve el índice mid.
    • Si A[mid] < X, descarte la mitad izquierda de los elementos y establezca lo como mid+1.
    • De lo contrario, si A[mid] > X, descarte la mitad derecha de los elementos y establezca hi como mid-1.
  • 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 como 0 y hi como n-1.
  • si lo > hi, hemos agotado el espacio de búsqueda del array, devuelve -1.
  • Calcula el punto medio mid como lo+(hi-lo)/2. Dividel array en dos partes: la mitad inferior con elementos de 0 a mid - 1, y la mitad superior con elementos de mid a n - 1.
  • Si X == mid, hemos encontrado que el elemento de destino devuelve mid.
  • Si X es menor que mid, busca en la mitad inferior del array llamando de forma recursiva a binarysearch(arr, lo, mid-1).
  • De lo contrario, si X es mayor que mid, busque en la mitad superior del array llamando de forma recursiva a binarysearch(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
¿Disfrutas de nuestros tutoriales? Suscríbete a DelftStack en YouTube para apoyarnos en la creación de más guías en vídeo de alta calidad. Suscríbete
Autor: Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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

Artículo relacionado - Java Algorithm