Java-Binär Suche interaktiv und rekursiv

  2. How-To's
  3. Java-Howtos
  4. Java-Binär Suche interaktiv und rekursiv
Harshit Jindal 12 Oktober 2023
Java Java Algorithm
  1. Iterativer binärer Suchalgorithmus
  2. Java-Iterationsprogramm für binäre Suche
  3. Rekursiver binärer Suchalgorithmus
  4. Java Rekursives Programm für binäre Suche
  5. Arrays.binarySearch() Überblick
  6. Java-Programm für binäre Suche
Java-Binär Suche interaktiv und rekursiv
Hinweis
Wenn Sie die Binäre Suche im Detail verstehen wollen, lesen Sie den Artikel Binärer Suchalgorithmus.

Iterativer binärer Suchalgorithmus

Nehmen wir an, wir haben ein unsortiertes Array A[], das n Elemente enthält, und wir wollen ein Element X finden.

  • Setzen Sie lo auf 0 und hi auf n - 1.
  • Während lo < hi:
    • Setzen Sie Mitte = lo + (hi - lo)/2.
    • Wenn A[mid] == X , haben wir das Element gefunden und geben den Index mid zurück.
    • Wenn A[mid] < X , dann verwerfen wir die linke Hälfte der Elemente und setzen lo als mid+1.
    • Wenn A[mid] > X, dann verwerfe die rechte Hälfte der Elemente und setze hi als mid-1.
  • Element wird nicht gefunden, also gebe -1 zurück.

Java-Iterationsprogramm für binäre Suche

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);
  }
}

Ausgabe:

Element found at index: 4

Rekursiver binärer Suchalgorithmus

Nehmen wir an, wir haben ein unsortiertes Array A[], das n Elemente enthält, und wir wollen ein Element X finden.

  • Initialisieren Sie lo als 0 und hi als n-1.
  • wenn lo >hi, haben wir den Array-Suchraum erschöpft, Rückgabe -1.
  • Berechnen Sie den Mittelpunkt mid als lo+(hi-lo)/2. Er teilt das Array in zwei Teile: die untere Hälfte mit Elementen von 0 bis mid - 1, und die obere Hälfte mit Elementen von mid bis n - 1.
  • Wenn X == mid ist, haben wir das Zielelement gefunden und geben mid zurück.
  • Wenn X kleiner als mid ist, suchen wir in der unteren Hälfte des Arrays, indem wir rekursiv binarysearch(arr, lo, mid-1) aufrufen.
  • Wenn X größer als mid ist, suchen Sie die obere Hälfte des Arrays, indem Sie rekursiv binarysearch(arr, mid+1, hi) aufrufen.

Java Rekursives Programm für binäre Suche

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);
  }
}

Ausgabe:

Element found at index: 1

Arrays.binarySearch() Überblick

Java stellt uns eine fertige Funktion Arrays.binarySearch() zur Verfügung, so dass wir die Funktion nicht selbst implementieren müssen. Es ist eine sehr einfach zu bedienende und effizient implementierte Methode und sie ist nicht fehleranfällig.

Syntax

public static int binarySearch(T arr, T key)

T kann einer der folgenden Werte sein: int, float, short, long, byte, char, double, und sogar ein benutzerdefiniertes Object dazu.

Genau wie unsere implementierte binäre Suche erfordert auch sie, dass das Array sortiert ist, sonst sind die Ergebnisse undefiniert. Sie durchsucht das Array mit Hilfe des binären Suchalgorithmus und findet den Index des Zielelements. Wenn es mehrere Vorkommen des Zielelements gibt, kann es den Index eines beliebigen von ihnen zurückgeben.

Parameter
Arr Das Eingabe-Array
Key Das Ziel-Element, nach dem gesucht wird.

Zurück

Wenn das Zielelement gefunden wird, wird sein Index zurückgegeben. Andernfalls wird beg - 1 zurückgegeben, wobei beg der Startindex des Array-Suchraums ist.

Java-Programm für binäre Suche

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);
  }
}

Ausgabe:

Element is found at index: 1
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

Verwandter Artikel - Java Algorithm