Arrays.binarySearch 메서드 알아보기

 

이진탐색 관련 문제를 풀던 중, Arrays에 binarySearch 메서드가 있는 걸 발견하였다!

원래는 직접 이진탐색을 구현하여 사용하였지만 컬렉션에서 지원된다면 사용하는 게 더 효율적일 것 같다.

그래서 이번엔 binarySearch 메서드를 알아보려고 한다.

 

 

정의

binarySearch 메서드를 타고 들어가보면 이렇게 긴 설명이 있다.

 

 

Searches the specified array of ints for the specified value using the binary search algorithm. The array must be sorted (as by the sort(int[]) method) prior to making this call. If it is not sorted, the results are undefined. If the array contains multiple elements with the specified value, there is no guarantee which one will be found. Params: a – the array to be searched key – the value to be searched for Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.


이진 검색 알고리즘을 사용하여 지정된 정수 배열에서 지정된 값을 검색합니다. 이 호출을 수행하기 전에 배열을 sort(int[]) 메서드로 정렬해야 합니다. 정렬되지 않은 경우 결과는 정의되지 않습니다. 배열에 지정된 값을 가진 여러 요소가 포함된 경우 어떤 요소가 발견될지 보장할 수 없습니다.
매개변수:
a - 검색할 배열
key - 검색할 값
반환: 검색 키가 배열에 포함된 경우 검색 키의 인덱스입니다. 그렇지 않으면 (-(삽입점) - 1)입니다. 삽입 지점은 키가 배열에 삽입되는 지점으로 정의됩니다. 즉, 키보다 큰 첫 번째 요소의 인덱스이거나 배열의 모든 요소가 지정된 키보다 작은 경우 a.length입니다. 이는 키가 발견된 경우에만 반환 값이 >= 0이 된다는 것을 보장합니다.

요약해보면 다음과 같다

 

1. 정렬을 일단 따로 해준다
2. Arrays.binarySearch 함수를 호출: (1)배열과 (2)찾으려는 key값을 넣는다
   • 값이 있으면 검색한 값의 인덱스가 나온다 (0보다 같거나 큰 값)
   • 값이 없으면 음수값이 나온다 ( -(내가 들어가야할 위치) -1 지점)
     • 즉, 내가 들어갈 수 있는 위치는 -return값 + 1 인덱스임 

 

값이 없으면 삽입 위치가 나온다는 점에서, 배열에 내가 찾고자 하는 값이 없다고 해도 나의 대략적 위치를 파악할 수 있다는 걸 알 수 있다. 대략적 위치는 이런 경우에 활용할 수 있을 것 같다.

• 배열에서 어떤 값과 차이가 가장 작은 값을 찾기
• 나의 삽입 위치 찾기

 

 

 

사용법

사용법은 크게 2가지로 볼 수 있겠다

• 원하는 값 이진탐색으로 찾기 -> return값이 0보다 큰 지만 확인
• 내가 삽입될 위치 찾기 -> return값이 음수인지 확인

 

 

 

사용예시

1. 원하는 값 인덱스 찾기(중복x)

int[] arr = new int[]{1,2,3,4,5,10,11};

System.out.println(Arrays.binarySearch(arr, 1)); //0

• 1을 찾았을 때 원하는 인덱스인 0이 잘 출력된다

 

2. 원하는 값 인덱스 찾기(중복ㅇ)

int[] arr = new int[]{1,2,3,3,4,5,10,11};

System.out.println(Arrays.binarySearch(arr, 3)); //3

int[] arr2 = new int[]{1,2,3,3,3,4,5,10,11};

System.out.println(Arrays.binarySearch(arr2, 3)); //4

• 중복값이 있으면 그중 이진탐색으로 가장 먼저 찾은 값의 인덱스를 출력하는 것 같다

 

3. 내가 삽입될 위치 찾기

int[] arr = new int[]{1,2,3,4,5,10,11};

System.out.println(Arrays.binarySearch(arr, 7)); //-6

• 7이 삽입되어야할 위치는 인덱스 5이다
• binarySearch 결과로 -6이 나왔음 (-위치-1 의 값)

 

 

이진탐색에 익숙해질 때까진 직접 구현해서 사용하고, 간단한 이진탐색 문제는 이 메서드를 사용하는 게 훨씬 좋을 것 같다!