배열.바이너리검색() 메소드는 이진 검색 알고리즘을 사용하여 지정된 데이터 유형의 지정된 배열에서 지정된 값을 검색합니다. 배열은 다음과 같이 정렬되어야 합니다. 배열.정렬() 호출하기 전에 메서드를 사용하세요. 정렬되지 않은 경우 결과는 정의되지 않습니다. 배열에 지정된 값을 가진 여러 요소가 포함된 경우 어떤 요소가 발견될지 보장할 수 없습니다. 다음과 같이 아래 제공된 그림을 살펴보겠습니다.
삽화:
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> Java에서 정렬된 배열의 요소를 찾는 가장 간단하고 효율적인 방법입니다.
통사론:
public static int binarySearch(data_type arr, data_type key)>
기억하다: 여기서 데이터 유형은 byte, char, double, int, float, short, long 및 심지어 object와 같은 기본 데이터 유형 중 하나일 수 있습니다.
매개변수:
- 검색할 배열
- 검색할 값
반환 유형: 배열에 포함된 경우 검색 키의 인덱스입니다. 그렇지 않으면 (-(삽입 지점) – 1)입니다. 삽입 지점은 키가 배열에 삽입되는 지점으로 정의됩니다. 즉, 키보다 큰 첫 번째 요소의 인덱스이거나 배열의 모든 요소가 지정된 키보다 작은 경우 a.length입니다. 이는 키가 발견된 경우에만 반환 값이>= 0이 된다는 것을 보장합니다.
다음과 같이 명심해야 할 몇 가지 중요한 사항이 있습니다.
- 입력 목록이 정렬되지 않으면 결과가 정의되지 않습니다.
- 중복된 항목이 있으면 어느 항목이 발견될지 보장할 수 없습니다.
위에서 우리는 이미 이 알고리즘을 작동할 수 있다는 것을 논의했습니다. Arrays.binarysearch() 대 Collections.binarysearch() . Arrays.binarysearch()는 기본 데이터 유형일 수 있는 배열에도 작동합니다. 컬렉션 .binarysearch()는 다음과 같은 객체 컬렉션에 대해 작동합니다. 배열목록 그리고 링크드리스트 .
예시 1:
자바
자바 데이터 유형
// 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));> >}> }> |
>
>산출
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>
복잡성 분석:
시간 복잡도:
Arrays.binarySearch() 메서드의 시간 복잡도는 O(log n)입니다. 여기서 n은 입력 배열의 길이입니다. 이는 이 방법이 이진 검색 알고리즘을 사용하여 정렬된 배열에서 대상 요소를 찾기 때문입니다.
보조 공간:
Arrays.binarySearch() 메서드에서 사용하는 보조 공간은 검색 작업을 수행하는 데 입력 배열 외에 추가 공간이 필요하지 않으므로 O(1)입니다.
문자열의 배열
검색할 배열 범위를 지정할 수도 있는 이 방법의 변형이 있습니다. 이에 대해서는 이후 게시물에서 객체 배열 검색과 함께 논의할 것입니다.
예시 2:
자바
SQL의 대소 문자는 무엇입니까
// 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);> >}> }> |
>
>산출
2>
복잡성 분석:
시간 복잡도:
Collections 클래스의 BinarySearch() 메서드의 시간 복잡도는 O(log n)입니다. 여기서 n은 목록의 요소 수입니다.
보조 공간:
Collections 클래스의 BinarySearch() 메서드는 추가 공간이 필요하지 않으므로 O(1)의 보조 공간 복잡도를 갖습니다.