Java-Binär Suche interaktiv und rekursiv
- Iterativer binärer Suchalgorithmus
- Java-Iterationsprogramm für binäre Suche
- Rekursiver binärer Suchalgorithmus
- Java Rekursives Programm für binäre Suche
-
Arrays.binarySearch()
Überblick - Java-Programm für binäre Suche
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
auf0
undhi
aufn - 1
. -
Während
lo
<hi
:- Setzen Sie
Mitte
=lo + (hi - lo)/2
. - Wenn
A[mid] == X
, haben wir das Element gefunden und geben den Indexmid
zurück. - Wenn
A[mid] < X
, dann verwerfen wir die linke Hälfte der Elemente und setzenlo
alsmid+1
. - Wenn
A[mid] > X
, dann verwerfe die rechte Hälfte der Elemente und setzehi
alsmid-1
.
- Setzen Sie
-
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
als0
undhi
alsn-1
. -
wenn
lo
>hi
, haben wir den Array-Suchraum erschöpft, Rückgabe-1
. -
Berechnen Sie den Mittelpunkt
mid
alslo+(hi-lo)/2
. Er teilt das Array in zwei Teile: die untere Hälfte mit Elementen von0
bismid - 1
, und die obere Hälfte mit Elementen vonmid
bisn - 1
. -
Wenn
X
==mid
ist, haben wir das Zielelement gefunden und gebenmid
zurück. -
Wenn
X
kleiner alsmid
ist, suchen wir in der unteren Hälfte des Arrays, indem wir rekursivbinarysearch(arr, lo, mid-1)
aufrufen. -
Wenn
X
größer alsmid
ist, suchen Sie die obere Hälfte des Arrays, indem Sie rekursivbinarysearch(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
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