이분 탐색 Arrays.binarySearch() 메서드 정의 및 사용 방법

알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서 반으로 쪼개면서 특정한 값을 찾아내는 알고리즘입니다.

 

이분 탐색 과정

목표값은 42로 설정하고 아래와 같은 배열이 있다고 가정해보겠습니다. 

 

1. 배열의 중간 '25'을 기준으로 목표값 '42'의 크기를 비교한다.

2. 목표값 '42'가 중간값 '25'보다 크기 때문에 mid+1을 low로 변경 후 다시 중간값을 찾는다.

3. 목표값 '42'가 중간값 '59'보다 작기 때문에 mid-1을 high로 변경 후 다시 중간값을 찾는다.

4. 목표값인 '42'가 중간값이랑 일치. 

※ 위와 같이 계속 중간값(mid)을 기준으로 크기를 비교해서 low값과 high값을 ±1을 시키면서 일치하게 만든다.

 

Arrays.binarySearch(배열, 찾는값);

 

자바에서는 이분 탐색을 지원하는 메서드가 있습니다. 

배열에 찾는값이 존재하면 요소의 인덱스를 반환하고, 찾는값이 없다면 음수의 숫자를 반환함.

위 메서드를 사용할 때 주의할 점은 배열을 오름차순으로 꼭 정렬해야합니다. 이분 탐색의 기본은 오름차순 정렬입니다. 만약에 정렬을 하지 않고 돌리게 되면 결과값이 크게 달라질 수 있습니다.

 

Arrays.binarySearch(배열, 1);  // 0
Arrays.binarySearch(배열, 3);  // 1
Arrays.binarySearch(배열, 7);  // 2 
Arrays.binarySearch(배열, 10); // 3

위와 같이 Arrays.binarySearch() 메서드를 사용하게 되면 해당 인덱스값을 찾아서 반환하게 됩니다. 하지만 해당값이 없을 때 반환되는 값은 주의해야할 필요가 있습니다.

 

Arrays.binarySearch(배열, -1); // -1
Arrays.binarySearch(배열, 2);  // -2
Arrays.binarySearch(배열, 4);  // -3
Arrays.binarySearch(배열, 5);  // -3
Arrays.binarySearch(배열, 15); // -4

인덱스 0의 값보다 작은 값은 전부 -1로 반환되고, 배열의 마지막 인덱스 3의 값보다 큰 값은 전부 -4로 반환됩니다. 찾으려는 값과 해당 인덱스의 값을 비교해서 음수의 숫자를 반환하고 있습니다. 글만 보시면 이해가 잘 안가실 수 있으니까 한 번 해보시는 걸 추천드립니다.