Arrays.binarySearch() 사용

지금까지 매번 구현해서 사용했는데 Arrays API에 이분탐색 함수가 있었다. 좀 찾아볼걸. 하지만 일반적으로 자주 구현하던 방식이랑 차이가 있어서 주의해야하는 부분이 있다.

일단 나는 이분 탐색은 무조건 양수를 반환하게 구현한데 반해서 Arrays 라이브러리에 포함된 binarySearch() 함수는 음수값을 반환하는 경우가 있다. 이게 우리가 원하는 타겟이 딱 맞게 존재하는 경우에는 양수가 반환되는데 정확히 같은 값이 아니면 배열에서 자기 위치를 찾아 음수로 반환한다는 특징이 있다.

예를 들어 2, 4, 7, 9 이라는 숫자 배열이 있다고 하자. 배열이 0부터 시작하는 경우, 정상적으로 이분 탐색이 이뤄진다면 2를 찾을 때 0을 반환하고, 9를 찾는다면 3을 반환할 것이다. 이것은 일반적인 탐색 결과와 크게 차이가 없다. 하지만 배열에 포함이 되지 않는 1이나 5를 찾는다면 어떻게 될까. Arrays.binarySearch()는 이때 그 값의 적절한 위치를 리턴해주되 배열에는 포함되지 않았다는 신호를 음수로 돌려줌으로써 표시해준다.

	0		1		2		3
1	2	3	4	5	7	8	9	10
-1		-2		-3		-4		-5

위 표를 보면 파란색으로 표시된 숫자는 배열에 포함되어있던 숫자이고, 빨간색 숫자는 포함되지 않던 숫자이다. 이 때 이분 탐색을 실행하면 각 숫자들에 매칭되는 0 ~ 3, 그리고 -1 ~ -5까지의 숫자가 리턴되게 된다. 이를 이용해서 배열에 특정 숫자가 포함되었는지 여부와 만일 포함되지 않았다면 그 숫자의 적절한 위치까지 찾아주는 것이 가능하다.

원리를 이해하기 위해서 이분 탐색을 구현할 줄 알아야하고, 또한 API를 사용할 수 없는 경우에 대비해서 구현하는 것은 당연하지만 굳이 어렵게 매번 구현할 필요는 없을듯하다.

실제 Arrays 안에 구현된 binarySearch() 코드는 아래와 같다.

	public static int binarySearch(int[] a, int fromIndex, int toIndex, int key) {
		rangeCheck(a.length, fromIndex, toIndex);
		return binarySearch0(a, fromIndex, toIndex, key);
	}

	// Like public version, but without range checks.
	private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) {
		int low = fromIndex;
		int high = toIndex - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			int midVal = a[mid];

			if (midVal < key)
				low = mid + 1;
			else if (midVal > key)
				high = mid - 1;
			else
				return mid; // key found
		}
		return -(low + 1); // key not found.
	}