Tablice.binarySearch() Metoda przeszukuje określoną tablicę danego typu danych pod kątem określonej wartości przy użyciu algorytmu wyszukiwania binarnego. Tablicę należy posortować według Tablice.sort() metodę przed wykonaniem tego połączenia. Jeśli nie jest posortowany, wyniki są niezdefiniowane. Jeśli tablica zawiera wiele elementów o określonej wartości, nie ma gwarancji, który z nich zostanie znaleziony. Prześledźmy ilustrację przedstawioną poniżej w następujący sposób.
Ilustracja:
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> Jest to najprostsza i najskuteczniejsza metoda znalezienia elementu w posortowanej tablicy w Javie
Składnia:
public static int binarySearch(data_type arr, data_type key)>
Pamiętać: Tutaj typem danych może być dowolny prymitywny typ danych, taki jak byte, char, double, int, float, short, long, a nawet object.
Parametry:
- Tablica, która ma zostać przeszukana
- Wartość, która ma być wyszukiwana
Typ zwrotu: indeks klucza wyszukiwania, jeśli jest zawarty w tablicy; w przeciwnym razie (-(punkt wstawienia) – 1). Punkt wstawienia definiuje się jako punkt, w którym klucz zostanie wstawiony do tablicy: indeks pierwszego elementu większy niż klucz lub a.length jeśli wszystkie elementy w tablicy są mniejsze niż określony klucz. Należy pamiętać, że gwarantuje to, że wartość zwracana będzie>= 0 wtedy i tylko wtedy, gdy klucz zostanie znaleziony.
Należy pamiętać o kilku ważnych kwestiach:
- Jeśli lista wejściowa nie jest posortowana, wyniki są niezdefiniowane.
- Jeśli istnieją duplikaty, nie ma gwarancji, który z nich zostanie znaleziony.
Jak wyżej, omówiliśmy już, że możemy obsługiwać ten algorytm Arrays.binarysearch() vs Kolekcje.binarysearch() . Arrays.binarysearch() działa w przypadku tablic, które mogą być również prymitywnymi typami danych. Kolekcje .binarysearch() działa dla kolekcji obiektów takich jak Lista tablic I Połączona lista .
Przykład 1:
Jawa
sztuczna inteligencja i inteligentni agenci
chmod 755
// Java program to demonstrate working of Arrays.> // binarySearch() in a sorted array> // Importing Arrays class from> // java.util package> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring and initializing byte arrays> >// to search over them> >byte> byteArr[] = {>10>,>20>,>15>,>22>,>35> };> >char> charArr[] = {>'g'>,>'p'>,>'q'>,>'c'>,>'i'> };> >int> intArr[] = {>10>,>20>,>15>,>22>,>35> };> >double> doubleArr[] = {>10.2>,>15.1>,>2.2>,>3.5> };> >float> floatArr[] = {>10>.2f,>15>.1f,>2>.2f,>3>.5f };> >short> shortArr[] = {>10>,>20>,>15>,>22>,>35> };> >// Using sort() method of Arrays class> >// and passing arrays to be sorted as in arguments> >Arrays.sort(byteArr);> >Arrays.sort(charArr);> >Arrays.sort(intArr);> >Arrays.sort(doubleArr);> >Arrays.sort(floatArr);> >Arrays.sort(shortArr);> >// Primitive datatypes> >byte> byteKey =>35>;> >char> charKey =>'g'>;> >int> intKey =>22>;> >double> doubleKey =>1.5>;> >float> floatKey =>35>;> >short> shortKey =>5>;> >// Now in sorted array we will fetch and> >// return elements/indiciesaccessing indexes to show> >// array is really sorted> >// Print commands where we are implementing> >System.out.println(> >byteKey +>' found at index = '> >+ Arrays.binarySearch(byteArr, byteKey));> >System.out.println(> >charKey +>' found at index = '> >+ Arrays.binarySearch(charArr, charKey));> >System.out.println(> >intKey +>' found at index = '> >+ Arrays.binarySearch(intArr, intKey));> >System.out.println(> >doubleKey +>' found at index = '> >+ Arrays.binarySearch(doubleArr, doubleKey));> >System.out.println(> >floatKey +>' found at index = '> >+ Arrays.binarySearch(floatArr, floatKey));> >System.out.println(> >shortKey +>' found at index = '> >+ Arrays.binarySearch(shortArr, shortKey));> >}> }> |
>
>Wyjście
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>
Analiza złożoności:
Złożoność czasowa:
Złożoność czasowa metody Arrays.binarySearch() wynosi O(log n), gdzie n jest długością tablicy wejściowej. Dzieje się tak, ponieważ metoda wykorzystuje algorytm wyszukiwania binarnego do znalezienia elementu docelowego w posortowanej tablicy.
Przestrzeń pomocnicza:
Przestrzeń pomocnicza używana przez metodę Arrays.binarySearch() to O(1), ponieważ do wykonania operacji wyszukiwania nie wymaga ona żadnej dodatkowej przestrzeni poza tablicą wejściową.
Istnieją warianty tej metody, w których możemy również określić zakres tablicy, w której będziemy przeszukiwać. Omówimy to, a także wyszukiwanie w tablicy Object w kolejnych postach.
Przykład 2:
Jawa
listy w Javie
// Java Program to Illustrate binarySearch() method> // of Collections class> // Importing required classes> import> java.util.ArrayList;> import> java.util.Collections;> import> java.util.List;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Creating empty List> >List al =>new> ArrayList();> >// Adding elements to the List> >al.add(>12>);> >al.add(>53>);> >al.add(>23>);> >al.add(>46>);> >al.add(>54>);> >// Using binarySearch() method of Collections class> >// over random inserted element and storing the> >// index> >int> index = Collections.binarySearch(al,>23>);> >// Print and display the index> >System.out.print(index);> >}> }> |
>
>Wyjście
2>
Analiza złożoności:
Złożoność czasowa:
Złożoność czasowa metody binarySearch() w klasie Collections wynosi O(log n), gdzie n to liczba elementów na liście.
Przestrzeń pomocnicza:
Metoda binarySearch() w klasie Collections nie wymaga dodatkowej przestrzeni, a zatem ma złożoność przestrzeni pomocniczej wynoszącą O(1).