Java에서 컬렉션 이진 검색

1. 이진 검색의 기본 알고리즘
2. Java의 Collections.binarySearch() 구문
3. Java에서 Collections.binarySearch()를 사용한 검색 유형
4. 결론

Java Collections 클래스에는 정렬된 목록에서 개체의 위치를 반환하는 binarySearch()라는 내부 메서드가 있습니다. Collections binarySearch() 기능의 매개변수를 사용하면 스크립트의 다른 매개변수에 따라 차별화할 수 있습니다.

이진 검색 알고리즘은 Collections.binarySearch()에서 요청된 개체에 대해 제공된 목록을 검색하는 데 사용됩니다. 이 호출을 수행하기 전에 항목의 자연 순서를 사용하여 목록을 오름차순으로 정렬해야 합니다.

정렬되지 않으면 결과가 명확하지 않습니다. 목록에 요청된 개체와 동일한 요소가 많이 포함되어 있는 경우 원하는 요소를 찾을 수 있는지 확실하지 않습니다.

이진 검색의 기본 알고리즘

이진 검색에서 컬렉션은 반복적으로 반으로 나뉩니다. 키 요소가 컬렉션의 중간 요소보다 작거나 큰지에 따라 컬렉션의 왼쪽 또는 오른쪽 절반에서 키 요소를 검색합니다.

이진 검색 알고리즘에서 따라야 할 단계:

1. 컬렉션의 중간 지점을 결정합니다.
2. 중간 요소와 필수 요소를 비교하십시오.
3. 키가 중간 요소와 동일한 경우 검색된 키의 중간 인덱스 위치를 반환합니다.
4. 그렇지 않으면 key > mid 요소인 경우 키는 컬렉션의 오른쪽 절반에 있습니다. 모음의 아래쪽(오른쪽) 절반을 완성하려면 1~3단계를 반복합니다.
5. 키가 중간 요소인 경우 키는 컬렉션의 위쪽 절반에 있습니다. 결과적으로 상반부에서 다시 이진 검색을 수행해야 합니다.

Java의 Collections.binarySearch() 구문

다음 구문은 이 메서드를 선언하는 데 사용됩니다.

public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
    T key) public static <T> int binarySearch(List<? extends T> list, T key,
    Comparator<? super T> c)

Collections.binarySearch() 메서드에는 두 가지 유형이 있습니다.

1. Java 컬렉션 binarySearch(List<? extends Comparable<? super T>> list, T key).

   절차를 사용하기 전에 제공된 자연수를 사용하여 목록을 오름차순으로 정렬해야 합니다. 목록이 정렬되지 않은 경우 결과를 정의할 수 없습니다.

2. Java 컬렉션 binarySearch(List<? extends T> list, T key, Comparator<? super T> c).

   프로시저를 호출하기 전에 제공된 비교기를 사용하여 목록을 오름차순으로 정렬해야 합니다.

Java에서 Collections.binarySearch()를 사용한 검색 유형

binarySearch()가 의도한 대로 작동하려면 제공된 비교기로 데이터를 정렬해야 합니다. 이 호출을 수행하기 전에 제공된 비교기를 사용하여 목록을 오름차순으로 정렬해야 합니다.

프로시저는 데이터가 정렬된 경우 찾는 요소의 인덱스를 제공합니다. 그렇지 않으면 (-(삽입점) - 1)을 반환합니다.

오름차순 목록에서 정수 키를 검색합니다.

예제 코드:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(3);
    al.add(4);
    al.add(5);
    al.add(20);
    al.add(30);

    int index = Collections.binarySearch(al, 20);
    System.out.println(index);

    index = Collections.binarySearch(al, 12);
    System.out.println(index);
  }
}

출력:

3
-4

내림차순 목록에서 정수 키를 검색합니다.

예제 코드:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
  public static void main(String[] args) {
    List<Integer> al = new ArrayList<Integer>();
    al.add(350);
    al.add(90);
    al.add(45);
    al.add(20);
    al.add(3);

    int index = Collections.binarySearch(al, 45, Collections.reverseOrder());

    System.out.println(index);
  }
}

출력:

2

결론

Collections binarySearch()는 가장 널리 사용되는 검색 방법입니다. 여기서 조건은 이진 검색이 성공하려면 데이터가 오름차순으로 정렬되어야 한다는 것입니다.

반복 또는 재귀 방법을 모두 사용하여 이진 검색을 구현할 수 있습니다. Java Arrays 클래스는 배열에서 이진 검색을 수행하는 binarySearch() 메서드를 추가로 제공합니다.