[자바] Collections.binarySearch 함수

개요

java.util.Collections.binarySearch() 함수는 정렬된 리스트에서 오브젝트의 위치를 반환하는 java.util.Collections 클래스 메소드입니다.

반드시 정렬 된 상태여야 합니다. 이진 탐색으로 값을 찾기 때문에 정렬이 되어 있지 않으면 이진 탐색을 할 수가 없습니다.

아래는 Java Doc에 명시된 내용입니다.

// Returns index of key in sorted list sorted in
// ascending order
public static int binarySearch(List slist, T key)

// Returns index of key in sorted list sorted in
// order defined by Comparator c.
public static int binarySearch(List slist, T key, Comparator c)

If key is not present, the it returns "(-(insertion point) - 1)".
The insertion point is defined as the point at which the key
would be inserted into the list.

요약

search 대상을 찾았을 때는 그 대상의 위치를,
만약 찾지 못했을때는 (- insertion point) - 1에 해당하는 값을 리턴하게 됩니다.

insertion point는 해당 리스트에 그 key가 존재 했다면, 그 key가 삽입되었을 위치를 말합니다.

지정한 comparator를 사용해 list의 요소를 비교할 수 없을때나, key를 비교할 수 없을 때 ClassCastException이 발생할 수 있습니다.

코드

import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
 
public class GFG
{
   public static void main(String[] args)
    {
        List al = new ArrayList();
        al.add(1);
        al.add(2);
        al.add(3);
        al.add(10);
        al.add(20);
 
       // 10 은 현재 3번째 위치에 있습니다.
        int index = Collections.binarySearch(al, 10);
        System.out.println(index);
 
       // 13 은 현재 없습니다. 13 은 4번째 위치에 추가 되었을 것 입니다.
        // 그래서 이 함수는 (-4-1)
        // 즉, -5를리턴하게 됩니다.
        index = Collections.binarySearch(al, 15);
        System.out.println(index);
    }
}

실행 결과

3
-5