[알고리즘] 탐색 알고리즘 - 이진 탐색 Binary Search

 

이진 탐색(Binary Search) 알고리즘 :

요소가 오름차순 또는 내림차순으로 정렬(sort)된 배열에서 원하는 키 값을 갖는 요소를 만날 때 까지 탐색.

선형 탐색보다 좀 더 빠르게 탐색 가능

 

값 53을 탐색

   1. 배열의 중앙 Binary[5] 와 비교, 53 > Binary[5]  =>  Binary[5] 이전 배열 탐색 대상에서 제외

   2. Binary[6] ~ Binary[10]의 중앙 Binary[8] 과 비교, 53 < Binary[8]  =>  Binary[8] 이후 배열 탐색 대상에서 제외

   3. Binary[6] ~ Binary[7]의 중앙 Binary[6] 과 비교, 53 == Binary[6]  =>  탐색 성공

배열 Binary 에서 이진 탐색 알고리즘으로 값 53 탐색

 

맨 앞의 인덱스를 pl, 맨 끝의 인덱스를 pr, 중앙 인덱스를 pc라고 할 때 탐색 시작시 pl은 0, pr은 n-1, pc는 (n-1)/2로 초기화.

검사한 요소를 하나씩 제외시키는 선형 탐색과 다르게 이진 탐색은 탐색을 한 단계씩 진행할 때 마다 탐색 범위가 반으로 줄어든다. 

Binary[pc]와 키 값을 비교하여 같으면 탐색 성공

 

1.Binary[pc] < key 일 때

  Binary[pl] ~ Binary[pc]는 key보다 작은 것이 분명하므로 탐색 범위를 중앙 요소 뒤쪽의 Binary[pc+1] ~ Binary[pr] 로 수정, pl을 pc+1로 업데이트

2. BSArray[pc] > key 일 때

  Binary[pc] ~ Binary[pr]는 key보다 큰 것이 분명하므로 탐색 범위를 중앙 요소 앞쪽의 Binary[pl] ~ Binary[pc-1] 로 수정, pr을 pc-1로 업데이트

 

이진 탐색의 종료 조건은 다음과 같다.

   조건 1 : Binary[pc]와 key가 일치할 경우 (탐색 성공)

   조건 2 : 탐색 범위가 더이상 존재하지 않는 경우 (탐색 실패)

배열의 요소 수가 n개 일 때 이진 탐색은 탐색을 반복할 때 마다 탐색 범위가 절반이 되므로 탐색에 필요한 비교 횟수의 평균값은 log n회 이다. => O(log n)

 

 

메서드 binSearch() : 배열 a 의 처음부터 끝까지 총 n개의 요소 중에서 값이 key인 요소를 이진 탐색

매개변수 : int[] a, int n, int key

반환값 : 키 값이 여러개 존재할 경우, 처음 발견한 요소의 인덱스를, 키 값이 존재하지 않으면 -1을 반환

 

   조건 1 : a[pc] == key (탐색 성공)

   조건 2 : pl > pr (탐색 범위가 존재하지 않음) (탐색 실패)

int binSearch(int[]a, int n, int key) {
	int pl = 0;
	int pr = n - 1;
	
	do {
		int pc = (pl + pr) / 2;
		if(a[pc] == key) {
			return pc;
		} else if (a[pc] < key) {
			pl = pc + 1;
		} else {
			pr = pc - 1;
		} 
	} while(pl <= pr);
	
	return -1;
}

 

 

 

 

이진 탐색 Binary Search : O(logN)