Arrays.binarySearch() methode doorzoekt de gespecificeerde array van het gegeven gegevenstype naar de gespecificeerde waarde met behulp van het binaire zoekalgoritme. De array moet worden gesorteerd volgens de Arrays.sort() methode voordat u deze oproep doet. Als het niet is gesorteerd, zijn de resultaten niet gedefinieerd. Als de array meerdere elementen met de opgegeven waarde bevat, is er geen garantie welke wordt gevonden. Laten we als volgt door de onderstaande illustratie glijden.

Illustratie:

Searching for 35 in byteArr[] = {10,20,15,22,35} will give result as 4 as it is the index of 35 Searching for g in charArr[] = {'g','p','q','c','i'} will give result as 0 as it is the index of 'g' Searching for 22 in intArr[] = {10,20,15,22,35}; will give result as 3 as it is the index of 22 Searching for 1.5 in doubleArr[] = {10.2,15.1,2.2,3.5} will give result as -1 as it is the insertion point of 1.5 Searching for 35.0 in floatArr[] = {10.2f,15.1f,2.2f,3.5f} will give result as -5 as it is the insertion point of 35.0 Searching for 5 in shortArr[] = {10,20,15,22,35} will give result as -1 as it is the insertion point of 5>

Het is de eenvoudigste en meest efficiënte methode om een ​​element in een gesorteerde array in Java te vinden

Syntaxis:

public static int binarySearch(data_type arr, data_type key)>

Herinneren: Hier kan het datatype elk van de primitieve datatypen zijn, zoals byte, char, double, int, float, short, long en zelfs object.

Parameters:

• De array waarin moet worden gezocht
• De waarde waarnaar moet worden gezocht

Retourtype: index van de zoeksleutel, als deze zich in de array bevindt; anders (-(invoegpunt) – 1). Het invoegpunt wordt gedefinieerd als het punt waarop de sleutel in de array zou worden ingevoegd: de index van het eerste element groter dan de sleutel, of a.length als alle elementen in de array kleiner zijn dan de opgegeven sleutel. Houd er rekening mee dat dit garandeert dat de retourwaarde>= 0 zal zijn als en alleen als de sleutel wordt gevonden.

Er zijn bepaalde belangrijke punten waarmee u rekening moet houden:

• Als de invoerlijst niet is gesorteerd, zijn de resultaten ongedefinieerd.
• Als er duplicaten zijn, is er geen garantie welke zal worden gevonden.

Zoals hierboven hebben we al besproken dat we dit algoritme ook kunnen gebruiken Arrays.binarysearch() vs Collecties.binarysearch() . Arrays.binarysearch() werkt voor arrays die ook van een primitief gegevenstype kunnen zijn. Collecties .binarysearch() werkt voor objecten Collecties zoals ArrayLijst En GelinkteLijst .

Voorbeeld 1:

Java

ontwerppatronen Java

>

hoe een kolom in postgresql te verwijderen

>

35 found at index = 4 g found at index = 1 22 found at index = 3 1.5 found at index = -1 35.0 found at index = -5 5 found at index = -1>

Complexiteitsanalyse:

Tijdcomplexiteit:
De tijdscomplexiteit van de methode Arrays.binarySearch() is O(log n), waarbij n de lengte van de invoerarray is. Dit komt omdat de methode een binair zoekalgoritme gebruikt om het doelelement in de gesorteerde array te vinden.

Hulpruimte:
De hulpruimte die door de methode Arrays.binarySearch() wordt gebruikt, is O(1), omdat er behalve de invoerarray geen extra ruimte nodig is om de zoekbewerking uit te voeren.

Er zijn varianten van deze methode waarin we ook het bereik van de array kunnen specificeren waarin we moeten zoeken. We zullen dat bespreken, evenals het zoeken in een Object-array in verdere berichten.

Voorbeeld 2:

Java

>

>

wat is alfabetnummer

2>

Complexiteitsanalyse:

Tijdcomplexiteit:
De tijdscomplexiteit van de methode binarySearch() in de klasse Collections is O(log n), waarbij n het aantal elementen in de lijst is.

Hulpruimte:
De methode binarySearch() in de klasse Collections vereist geen extra ruimte en heeft dus een hulpruimtecomplexiteit van O(1).