이진 검색(Binary Search)

이진 검색(Binary Search)

정렬되어 있는 배열에 대하여 원소들의 가운데 있는 항목을 키 값과 비교하여 키 값이 더 크면 오른쪽을, 더 작으면 왼쪽을 검색한다.

왼쪽과 오른쪽으로 나누어서 검색하면서 이진 검색을 다시 반복하여 검색 범위를 반으로 줄여나가면서 검색한다.

절반 두 부분으로 나누어 검색하므로 이분 검색, 보간 검색(Interpolation Search)이라고도 하며 분할 정복 기법이라고도 한다.

삽입이나 삭제 작업을 수행한 후에 항상 배열을 정렬해야한다.

시간 복잡도는 O(log2n)이다.

​

예시 1) 50을 찾는 경우

{2, 6, 16, 27, 32, 41, 50}

​

1. 가운데 원소인 27을 기준으로 키 값과 비교한다. 키 값이 더 크기 때문에 검색 범위를 기준 값의 오른쪽으로 정한다.

{2, 6, 16, 27, 32, 41, 50}

​

2. 검색 범위 중 가운데 원소인 41을 기준으로 키 값과 비교한다. 키 값이 더 크기 때문에 검색 범위를 기준 값의 오른쪽으로 정한다.

{2, 6, 16, 27, 32, 41, 50}

​

3. 검색 범위 중 가운데 즉 50이 키 값과 일치하기 때문에 검색을 종료한다.

{2, 6, 16, 27, 32, 41​, 50}

​

예시 2) 5를 찾는 경우

{2, 6, 16, 27, 32, 41, 50}

​

1. 가운데 원소인 27을 기준으로 키 값과 비교한다. 키 값이 더 작기 때문에 검색 범위를 기준 값의 왼쪽으로 정한다.

{2, 6, 16, 27, 32, 41, 50}

​

2. 검색 범위 중 가운데 원소인 6을 기준으로 키 값과 비교한다. 키 값이 더 작기 때문에 검색 범위를 기준 값의 왼쪽으로 정한다.

{2, 6, 16, 27, 32, 41, 50}

​

3. 남은 원소가 키 값과 다르기 때문에 검색 실패로 종료한다.

​

프로그램 작성)

package test;

class Search {
	public void binarySearch(int[] a, int low, int high, int key) {
		if(low > high) {
			System.out.printf("%d 찾지 못함.", key);
			return;
		}
		
		int middle = (low+high)/2;
		
		if(key < a[middle]) {
			binarySearch(a, low, middle-1, key);
		} else if(key > a[middle]) {
			binarySearch(a, middle+1, high, key);
		} else {
			System.out.printf("%d 찾음.", a[middle]);
			return;
		}
		
	}
}

public class Test {
	public static void main(String[] args) {
		int[] a = {2, 6, 16, 27, 32, 41, 50};

		System.out.println("정렬된 배열 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Search s = new Search();
		s.binarySearch(a, 0, a.length, 50);
		System.out.println();

		s.binarySearch(a, 0, a.length, 5);
		System.out.println();
	}
}

실행 결과)