이진 검색은 입력이 정렬될 때 적용되는 검색 기술 중 하나입니다. 여기서는 요소가 이미 정렬되어 있으므로 왼쪽으로 갈지 오른쪽으로 갈지 참조 프레임 역할을 하는 중간 요소를 찾는 데 중점을 둡니다. 이 검색은 매 반복마다 검색 기술을 최적화하는 데 도움이 되며 이진 검색이라고 하며 질문 해결에 간접적으로 적용되므로 독자는 이에 대해 스트레스를 받습니다.
Java의 이진 검색 알고리즘
다음은 이진 검색을 위해 설계된 알고리즘입니다.
- 시작
- 입력 배열 및 대상 가져오기
- 시작 = 0 및 끝 = (배열 크기 -1) 초기화
- 인도화 중간 변수
- 중간 = (시작+끝)/2
- array[ mid ] == target이면 mid를 반환합니다.
- 만약 배열[ mid ]
- 배열[ mid ]> target이면 end = mid-1
- start<=end인 경우 5단계로 이동
- 요소를 찾을 수 없음으로 -1을 반환합니다.
- 출구
이제 입력이 정렬되지 않으면 결과가 정의되지 않을 것이라고 생각해야 합니다.
메모: 중복된 항목이 있으면 어느 항목이 발견될지 보장할 수 없습니다.
Java 바이너리 검색 방법
Java에는 구현하는 세 가지 메소드가 있습니다. 이진 검색 Java에서는 다음과 같이 언급됩니다.
- 반복 방법
- 재귀적 방법
- 내장 방법
1. Java의 이진 검색을 위한 반복 방법
아래에 언급된 구현은 다음과 같습니다.
자바
// Java implementation of iterative Binary Search> class> BinarySearch {> >// Returns index of x if it is present in arr[l....r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >while> (l <= r) {> >int> mid = (l + r) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x) {> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >// so we decrease our r pointer to mid - 1> >}>else> if> (arr[mid]>x) {> >r = mid ->1>;> >// Else the element can only be present> >// in right subarray> >// so we increase our l pointer to mid + 1> >}>else> {> >l = mid +>1>;> >}> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// Driver method to test above> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(>'Element not present'>);> >else> >System.out.println(>'Element found at index '> >+ result);> >}> }> |
>
>산출
쉘 스크립트의 for 루프
Element found at index 3>
팁: 괴짜 여러분은 다음과 같은 기능이 있는지 궁금할 것입니다. 하한() 또는 상한() C++ STL에서 발견되었을 가능성이 높습니다. 그래서 정답은 Java 9까지만 기능이 없었고 나중에 추가되었다는 것입니다.
2. 이진 검색을 위한 재귀적 방법
위 메소드를 구현하면 다음과 같습니다.
자바
// Java implementation of> // recursive Binary Search> // Driver Class> class> BinarySearch {> >// Returns index of x if it is present in arr[l..> >// r], else return -1> >int> binarySearch(>int> arr[],>int> l,>int> r,>int> x)> >{> >if> (r>= l) {> >int> mid = l + (r - l) />2>;> >// If the element is present at the> >// middle itself> >if> (arr[mid] == x)> >return> mid;> >// If element is smaller than mid, then> >// it can only be present in left subarray> >if> (arr[mid]>x)> >return> binarySearch(arr, l, mid ->1>, x);> >// Else the element can only be present> >// in right subarray> >return> binarySearch(arr, mid +>1>, r, x);> >}> >// We reach here when element is not present> >// in array> >return> ->1>;> >}> >// main function> >public> static> void> main(String args[])> >{> >BinarySearch ob =>new> BinarySearch();> >int> arr[] = {>2>,>3>,>4>,>10>,>40> };> >int> n = arr.length;> >int> x =>10>;> >int> result = ob.binarySearch(arr,>0>, n ->1>, x);> >if> (result == ->1>)> >System.out.println(> >'Element is not present in array'>);> >else> >System.out.println(> >'Element is present at index '> + result);> >}> }> |
>
>산출
Element is present at index 3>
위 방법의 복잡성
시간 복잡도: 오(로그 N)
공간 복잡도: O(1), 재귀 호출 스택을 고려하면 보조 공간은 O(log N)입니다.
3. Java에서 이진 검색을 위한 빌드 방법
배열.바이너리검색() 기본 데이터 유형일 수 있는 배열에서도 작동합니다.
위 메소드를 구현하면 다음과 같습니다.
자바
// Java Program to demonstrate working of binarySearch()> // Method of Arrays class In a sorted array> // Importing required classes> import> java.util.Arrays;> // Main class> public> class> GFG {> >// Main driver method> >public> static> void> main(String[] args)> >{> >// Declaring an integer array> >int> arr[] = {>10>,>20>,>15>,>22>,>35> };> >// Sorting the above array> >// using sort() method of Arrays class> >Arrays.sort(arr);> >int> key =>22>;> >int> res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>40>;> >res = Arrays.binarySearch(arr, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>산출
22 found at index = 3 40 Not found>
Java 컬렉션의 이진 검색
이제 LinkedList에서 Collections.binarySearch()가 어떻게 작동하는지 살펴보겠습니다. 따라서 기본적으로 위에서 설명한 대로 이 메서드는 ArrayList와 같은 임의 액세스 목록에 대해 log(n) 시간에 실행됩니다. 지정된 목록이 RandomAccess 인터페이스를 구현하지 않고 크기가 큰 경우 이 메서드는 O(n) 링크 순회 및 O(log n) 요소 비교를 수행하는 반복자 기반 이진 검색을 수행합니다.
Collections.binarysearch() 다음과 같은 개체 컬렉션에서 작동합니다. 배열목록 그리고 링크드리스트 .
위 메소드를 구현하면 다음과 같습니다.
자바
// Java Program to Demonstrate Working of 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 an empty ArrayList of integer type> >List al =>new> ArrayList();> >// Populating the Arraylist> >al.add(>1>);> >al.add(>2>);> >al.add(>3>);> >al.add(>10>);> >al.add(>20>);> >// 10 is present at index 3> >int> key =>10>;> >int> res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >key =>15>;> >res = Collections.binarySearch(al, key);> >if> (res>=>0>)> >System.out.println(> >key +>' found at index = '> + res);> >else> >System.out.println(key +>' Not found'>);> >}> }> |
>
>산출
10 found at index = 3 15 Not found>
위 방법의 복잡성
시간 복잡도 : O(로그 N)
보조 공간 : ㅇ(1)