자바로 구현하는 이진탐색 (BinarySearch) 알고리즘

이진탐색 (binary Search)

 

이진 검색 알고리즘(binary search algorithm)은 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다.

처음 중간의 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고 작음을 비교하는 방식을 채택하고 있다.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다.

검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 된다. 이진 검색은 분할 정복 알고리즘의 한 예이다.

 

(자바에서는 java.util.Arrays 클래스에 자바 1.2 부터 binarySearch 관련 메소드를 제공하고 있습니다.)

 

 

진행 순서

ex) 1,2,3,4,5,6 순서의 배열 중 5를 찾는다는 가정

 

1. 중간값을 임의 값으로 선택 (3)

2. 찾고자 하는 값(5) 와 중간값(3) 을 비교하여 찾는값이 중간값보다 작다면 왼쪽에서 중간 요소를 다시 선택,

반대로 찾고자 하는 값이 중간값보다 큰 경우 오른쪽에서 중간요소 다시 선택

위 에서는 찾고자 하는 값(5) 가 중간요소(3) 보다 크므로 오른쪽에서 요소 다시 선택

3. 요소 (4,5,6) 에서 중간요소 는 5 이므로 다시 찾고자 하는 값 5 와 비교하는데 값이 일치하므로 탐색 종료

 

자바 소스코드

 

	public static int binarySearch(int[] array, int key) {
		int low = 0;
		int high = array.length - 1;

		while (low <= high) {
			int mid = (low + high) >>> 1;
			int midVal = array[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.
	}
	
	//재귀호출 스타일
	public static int binarySearch(int[] array, int fromIndex, int toIndex, int key) {
		
		if (toIndex < fromIndex)
			return -1; // key not found.
		
		int mid = (toIndex+fromIndex) >>> 1;

		//찾고자 하는 값이 중간요소 보다 작은경우
		if (array[mid] > key)
			return binarySearch(array, fromIndex, mid-1, key);
		//찾고자 하는 값이 중간요소 보다 큰경우
		else if (array[mid] < key)
			return binarySearch(array, mid+1, toIndex, key);
		else 
			return mid; // key found
	}