이진 탐색(Binary Search)

이진 탐색(이분 탐색, Binary Search)이란 정렬된 자료를 절반씩 쪼개어 탐색하는 탐색 방법을 이야기합니다. 이진 탐색은 모든 값을 탐색하는 일반 탐색과 달리 O(logN) 의 시간복잡도를 갖기 때문에 정렬된 자료에 대해 매우 빠른 탐색속도를 갖습니다.

이진 탐색 방법

탐색 범위의 시작과 끝 인덱스를 구하고, 두 인덱스의 중간값을 구해서 그 중간값이 찾으려는 값보다 큰지 작은지에 따라 탐색의 범위를 좁힙니다.

찾으려는 값이 더 크다면 범위를 중간값부터 끝 인덱스까지로 정하고, 더 작다면 시작 값부터 중간 값의 인덱스로 정합니다.

위와 같은 과정을 반복하여 찾으려는 값이 중간값과 같다면 반환하고, 시작범위와 끝 범위가 교차되었는데도 못찾았다면, 찾지 못했음을 반환합니다.

이진 탐색 의사 코드

binarySearch(A[0..N-1], value) {//k
  low = 0
  high = N - 1
  while (low <= high) {
      mid = (low + high) / 2
      if (A[mid] > value)
          high = mid - 1
      else if (A[mid] < value)
          low = mid + 1
      else
          return mid // found k
  }
  return -1 // not found k
}

• low 와 high 를 첫번째 인덱스와 마지막 인덱스로 지정
• low 와 high 가 교차될 때까지 반복하며 교차될 때까지 못찾았다면 -1 을 반환하여 못찾았음을 알림
• 현재 low 와 high 의 중간 값으로 mid 값을 정하며 mid 인덱스의 값과 찾으려는 값을 비교하며 범위를 줄임

구현

의사 코드와 마찬가지로 자바에서 구현할 수 있습니다.

/*
	@params arr : 원소를 찾을 배열
	@params start : 탐색 시작 인덱스
	@params end : 탐색 마지막 인덱스
	@params key : 찾을 원소 값
*/
public static int binarySearch(int[] arr, int start, int end, int key) {
	int low = start;
	int high = end - 1;

	while(low <= high) {
		int mid = (low + high) >> 1;
		int midVal = arr[mid];
		if (midVal < key) {
			low = mid + 1;
		} else if (midVal == key){
			return mid;
		}
		else {
			high = mid - 1;
		}
	}

	//못찾았을 때
	//return -(high + 2); 와 같음
	return -(low + 1);
}

• low 인덱스와 high 인덱스의 범위를 줄여가면서 탐색
• 두 인덱스의 중간 인덱스(mid)보다 key 가 큰지 작은지에 따라 low 혹은 high 의 범위 감소
• key 가 mid 인덱스의 값과 같다면 mid 값 반환
• 모든 탐색을 끝내도 찾지 못한경우 (low > high ) 마지막으로 탐색했던 low 위치로 가장 key 값과 같은 값을 반환
• 이 때 못찾았음을 알리기 위해 음수부호를 붙이고, 0 번 인덱스를 반환할 수 있으므로 +1 해주어 구분

수행속도 확인

이진 탐색의 수행속도는 선형으로 배열을 탐색하는 방법에 비해 굉장히 빠릅니다. 직접 이진탐색을 수행하는 코드를 작성하여 수행시간의 차이를 알아봅니다.

1. 값 할당

유의미한 시간 차이를 확인하기 위해 6 * 10 ^ 8 의 크기를 갖는 배열을 선언합니다.

정렬된 자료를 저장해야하므로 인덱스와 같은 값을 저장하도록 합니다.

그 안에서 45 * 10 ^ 7 의 값을 담고 있는 인덱스를 찾습니다.

//6억 배열 선언
final int arraySize = 600_000_000;
int[] arr = new int[arraySize];

for(int i = 0; i < arr.length; i++){
	arr[i] = i;
}

//4.5억을 가르키고 있는 인덱스 값 찾기
int targetVal = 450_000_000;

2. 선형탐색

배열의 인덱스를 하나씩 탐색하면서 값이 일치하는 경우를 찾습니다. 수행 시간의 차이를 확인하기 위해 currentTimeMillis() 메서드를 사용합니다.

long start = System.currentTimeMillis();
//선형 탐색
for(int i = 0; i < arr.length; i++){
	if (arr[i] == targetVal) {
		System.out.println("탐색 성공! 인덱스 : " + i);
		break;
	}
}
long end = System.currentTimeMillis();
//선형 탐색 수행시간 출력
System.out.println("수행시간 : " + (end - start));

3. 이진 탐색

위에서 작성한 이진탐색 메서드로 수행시간을 확인합니다.

start = System.currentTimeMillis();
//이진 탐색
System.out.println("탐색 성공! 인덱스 : " + MyBinarySearch.binarySearch(arr, 0, arr.length - 1, targetVal));
end = System.currentTimeMillis();

//이진 탐색 수행시간 출력
System.out.println("수행시간 : " + (end - start));

4. 결과 확인

/*
출력 내용
	탐색 성공! 인덱스 : 450000000
	수행시간 : 195
	탐색 성공! 인덱스 : 450000000
	수행시간 : 1
*/

결과 출력은 위와 같이 확인할 수 있었으며 두 탐색 과정의 소요시간이 꽤 많이 차이나는 모습을 보여줍니다.

선형 탐색 과정은 O(N) 의 시간복잡도를 가지며 이진탐색은 O(NlogN) 의 복잡도를 가지기 때문에 위와 같은 시간 차이를 볼 수 있습니다.

LowerBound

이진 탐색 중 같은 값을 저장하는 요소가 여럿이라면 그 중 가장 작은 값을 갖는 인덱스를 반환하도록 할 수 있습니다.

/*
	@params arr : 원소를 찾을 배열
	@params start : 탐색 시작 인덱스
	@params end : 탐색 마지막 인덱스
	@params key : 찾을 원소 값
*/
public static int lowerBound(int[] arr, int start, int end, int key){
	int low = start;
	int high = end;

	while (low <= high){
		int mid = (low + high) >> 1;
		int midVal = arr[mid];
		if(midVal < key)        low = mid + 1;
//			else if(midVal == key)  return mid;
			//같으면 high가 줄어드니까 -> 로우는 안줄어들 -> lower_bound 역할
		else                    high = mid - 1;
	}

	return low;
}

일반적인 이진탐색과 다른점은 mid 값이 찾으려는 key 와 같더라도 계속 탐색을 수행하며 high 의 값만 줄이므로, 값이 같거나 크다면 low 의 값을 고정합니다.

따라서 반복문의 조건인 low <= high 를 만족하지 않을 때, low 인덱스가 갖는 값은 key 보다 작지 않은 최소의 값이라고 할 수 있습니다.

UpperBound

위 lowerBound 코드와 비슷한 원리로key 보다 작지 않으면서 가장 큰 인덱스를 갖는 값을 upperBound를 통해 찾을 수 있습니다.

/*
	@params arr : 원소를 찾을 배열
	@params start : 탐색 시작 인덱스
	@params end : 탐색 마지막 인덱스
	@params key : 찾을 원소 값
*/
public static int upperBound(int[] arr, int start, int end, int key) {
	int low = start;
	int high = end;

	while (low <= high) {
		int mid = (low + high) >> 1;
		int midVal = arr[mid];
		if(midVal > key)    high = mid - 1;
		//			else if(midVal == key)  return mid;
		//같으면 low가 커지니 -> upper_bound 역할
		else                low = mid + 1;
	}

	return high;
}

LowerBound, UpperBound 테스트

//key는 5로 할당
targetVal = 5;
//중복 요소를 넣기 위해 3개씩 같은 값 저장
for (int i = 0; i < arr.length ; i++) {
	arr[i] = i/3;
}
//배열 요소 확인
for (int i = 0; arr[i] <= 7 ; i++) {
	System.out.print("[" + arr[i] + "], ");
}
System.out.println();

//각각의 결과 확인
System.out.println(MyBinarySearch.binarySearch(arr, 0, arr.length - 1, targetVal));
System.out.println(MyBinarySearch.lowerBound(arr, 0, arr.length - 1, targetVal));
System.out.println(MyBinarySearch.upperBound(arr, 0, arr.length - 1, targetVal));

/*
	출력 
	[0], [0], [0], [1], [1], [1], [2], [2], [2], [3], [3], [3], [4], [4], [4], [5], [5], [5], [6], [6], [6], [7], [7], [7], 
	16
	15
	17
*/

일반 이진탐색은 같은 값을 찾자마자 반환하므로 16 번째 인덱스를 결과로 받았습니다.

이와 다르게 lowerBound는 가장 작은 인덱스인 15, upperBound는 17 의 인덱스를 반환하는 모습을 볼 수 있습니다.