Ricerca binaria Java interattiva e ricorsiva

Harshit Jindal 12 ottobre 2023 Java Java Algorithm
  1. Algoritmo di ricerca binaria iterativa
  2. Programma iterativo Java per la ricerca binaria
  3. Algoritmo di ricerca binaria ricorsiva
  4. Programma ricorsivo Java per la ricerca binaria
  5. Arrays.binarySearch() Panoramica
  6. Programma Java per la ricerca binaria
Ricerca binaria Java interattiva e ricorsiva
Nota
Se si desidera comprendere in dettaglio la ricerca binaria, fare riferimento all’articolo algoritmo di ricerca binaria.

Algoritmo di ricerca binaria iterativa

Supponiamo di avere un array non ordinato A[] contenente n elementi e di voler trovare un elemento X.

  • Imposta lo come 0 e hi come n - 1.
  • Mentre lo <hello:
    • Impostare mid = lo + (hi - lo)/2.
    • Se A[mid] == X, abbiamo trovato che l’elemento restituisce l’indice mid.
    • Se A[mid] < X, scartare la metà sinistra degli elementi e impostare lo come mid+1.
    • Altrimenti se A[mid] > X, scartare la metà destra degli elementi e impostare hi come mid-1.
  • L’elemento non è stato trovato, quindi restituisci -1.

Programma iterativo Java per la ricerca 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);
  }
}

Produzione:

Element found at index: 4

Algoritmo di ricerca binaria ricorsiva

Supponiamo di avere un array non ordinato A[] contenente n elementi e di voler trovare un elemento X.

  • Inizializza lo come 0 e hi come n-1.
  • se lo> hi, abbiamo esaurito lo spazio di ricerca dell’array, restituisce -1.
  • Calcola il punto medio mid come lo+(hi-lo)/2. Divide la matrice in due parti: la metà inferiore con elementi da 0 a metà - 1 e la metà superiore con elementi da metà a n - 1.
  • Se X == mid, abbiamo trovato che l’elemento target ritorna mid.
  • Se X è minore di mid, cerca nella metà inferiore dell’array chiamando ricorsivamente binarysearch(arr, lo, mid-1).
  • Altrimenti se X è maggiore di mid, cerca nella metà superiore dell’array chiamando ricorsivamente binarysearch(arr, mid+1, hi).

Programma ricorsivo Java per la ricerca 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);
  }
}

Produzione:

Element found at index: 1

Arrays.binarySearch() Panoramica

Java ci fornisce una funzione pronta per l’uso Arrays.binarySearch() in modo da non dover implementare la funzione da soli. È un metodo molto semplice da usare e implementato in modo efficiente e non è soggetto a errori.

Sintassi

public static int binarySearch(T arr, T key)

T può essere uno dei seguenti: int, float, short, long, byte, char, double e anche un Object definito dall’utente.

Proprio come la nostra ricerca binaria implementata, richiede anche che l’array sia ordinato altrimenti i risultati non sono definiti. Cerca nell’array utilizzando l ‘algoritmo di ricerca binaria e trova l’indice dell’elemento di destinazione. Se sono presenti più occorrenze dell’elemento target, può restituire l’indice di ognuna di esse.

Parametri
Arr La matrice di input
Key L’elemento target che stiamo cercando.

Ritorno

Se trova l’elemento di destinazione, restituisce il suo indice. Altrimenti, restituisce beg - 1 dove beg è l’indice iniziale dello spazio di ricerca dell’array.

Programma Java per la ricerca 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);
  }
}

Produzione:

Element is found at index: 1
Ti piacciono i nostri tutorial? Iscriviti a DelftStack su YouTube per aiutarci a creare altre guide video di alta qualità. Iscriviti
Autore: 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