[Java] 정렬된 배열에서 삽입 포인트 찾기 Arrays.binarySearch()

자바 배열을 사용하다 보면 원하는 값의 인덱스를 찾고 싶을 때가 있다. 이 때 Collection api를 사용한다면 다음과 같이 indexOf 메서드를 사용하면 된다.

List<Integer> abs = List.of(12, 14, 16);
int index = abs.indexOf(14);
System.out.println(index);
// 1

하지만 요소가 primitive 타입인 경우, List 자료형으로 만들기 위해 Integer와 같은 Wrapper 클래스로 형태를 변환해주어야 한다. Arrays.binarySearch() 메서드는 정렬된 배열 요소중 중복된 값이 없음이 보장 될 경우, Collection의 indexOf 와 같은 결과값을 얻을 수 있다.

 

binarySearch()

int[] numbers = {1, 3, 5, 9, 11, 15};
int index = Arrays.binarySearch(numbers, 11);
System.out.println(index);
// 4

Arrays는 배열을 보다 편하게 사용하기 위한 다양한 기능들을 제공한다. 그 중 binarySearch() 는 이진 탐색 알고리즘을 사용하여 파라미터로 넘겨받은 배열안에 있는 key를 찾아 인덱스를 반환한다. binarySearch 알고리즘 자체가 정렬된 요소 안에서만 유효한 알고리즘이기 때문에 정렬되지 않았다면 정상적으로 동작하지 않는다.

 

첫 번째로 조심해야될 점은 배열에 주어진 key 가 없을 경우이다. 

int[] numbers = {1, 3, 5, 9, 11, 15};
int index = Arrays.binarySearch(numbers, 12);
System.out.println(index);
// -6

numbers라는 배열엔 '12'라는 값이 없다. 이와 같이 주어진 배열에 key가 없을 경우, binarySearch는 해당 key가 삽입될 위치를 음수로 알려준다.  key가 없을 경우 반환되는 규칙은 다음을 참고하면 된다.

쉽게 생각해서 N 번째 요소 뒤에 위치하는 key는 -N 으로 반환된다고 생각하면 된다. 12는 15의 뒤에 위치해야한다. 15는 배열에서 6번째 값이기 때문에 -6 이라는 값이 반환되었다.

 

배열의 요소가 중복할 가능성이 있다면 binarySearch를 indexOf 처럼 사용하는 것이 불가능하다. 이유는 binary search 알고리즘의 동작 방식 때문이다. binary search는 주어진 요소를 반으로 나누어 탐색하는 알고리즘인데, 요소가 중복될 경우 탐색 과정에서 중복된 두번째, 세번째 요소의 인덱스를 반환할 수도 있기 때문이다. 

int[] numbers1 = {1, 3, 5, 9, 11, 11, 15};
System.out.println(Arrays.binarySearch(numbers1, 11));
// 5

int[] numbers2 = {1, 3, 5, 9, 11, 11, 11, 11, 15};
System.out.println(Arrays.binarySearch(numbers2, 11));
// 4

위 예시 코드처럼 '11'의 첫 번째 인덱스는 '4'이지만, 이진 탐색 과정에서 '5'라는 값이 반환된 것을 확인할 수 있다. 이렇듯 binarySearch 메서드는 중복된 요소를 갖는 배열에서 항상 첫 번째 인덱스값을 반환한다는 것을 보장하지 않는다. 따라서, 중복된 값이 있는 배열에서 첫 번째 요소값을 찾고 싶다면 Collection api를 사용해야한다.

 

Arrays.binarySearch 매서드는 상황에 따라 다양하게 사용될 수 있지만, 특히 중복된 값이 있을 경우 조심해서 사용해야한다.