[알고리즘] 이분 탐색(Binaray Search)

이분 탐색(Binary Search)

 

정렬되어 있는(이분 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때, 

 

순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라

 

탐색 범위를 절반씩 줄여가며 찾아가는 Search 방법이다.

 

작동예시

1 2 3 4 5 6라는 값에서 6을 찾고자 한다면

 

배열의 중간에 위치한 3이라는 값과 6을 비교한다.

 

6은 3보다 크므로, 이제 3의 왼쪽에 위치하는 값들은 탐색할 필요가 없으므로

(어차피 3 왼쪽에 있는 수들은 3보다 작기 때문이다)

 

3의 오른쪽에 있는 값들을 대상으로 탐색을 다시 시도한다.

 

이제 4 5 6이 남았으므로, 다시 중간값인 5와 찾고자 하는 대상인 6를 비교한다.

 

6은 5보다 크므로, 5의 오른쪽에 있는 값들을 대상으로만 탐색을 다시 시도한다.

 

이제 6만이 남았는데 6과 6을 비교하면, 값이 일치하므로 탐색을 종료한다.

 

자바 코드

 public static int binarySearch(int[] array, int target){

	int start= 0;
	int end= array.length-1;
	int mid= (end+start)/2;

	while(end-start>= 0){
		if(array[mid]== target){
			//Case: Find target in array
 			return mid;
		}else if(array[mid]<= target){
 			//Case: target is exist in right of array[mid]
			start= mid+1;
		}else{
			//Case: target is exist in left of array[mid]
 			end= mid-1;
 		}
 		mid= (end+start)/2;
 	}
 	//Case: Can't find data in array
 	return -1;
}

 

시간복잡도

 

처음부터 끝까지 원하는 값을 찾을 때까지 탐색을 계속하는 순차 탐색은 Worst Case일 때 O(n)이라는 Time Complexity를 보여준다.

 

10만개의 데이터가 있다면 무려 10만번을 탐색해야 하는 것이다.

 

그러나, Binary Search는 탐색 대상을 절반씩 계속해서 줄여나가기 때문에, Worst Case일 때에도 탐색의 횟수가 log₂n 이 되므로 

10만개의 데이터가 있다고 하더라도 약 16번 정도로 탐색을 끝낼 수 있다.

 

Time Complexity는 O(log n)이다.