이분 탐색 (Binary Search)

이분 탐색

• 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘
• 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 범위를 절반씩 줄이면서 대상을 찾는다.
• 시간 복잡도: $O(logN)$

 

이분 탐색 과정

이분 탐색을 위해서는 데이터셋이 정렬되어 있어야 한다. 데이터 셋은 아래와 같다. 

찾고자 하는 데이터(target)는 100이라고 가정하고 설명한다. 

 

1. 현재 데이터 셋의 중앙값을 선택한다.

 left는 데이터 셋의 시작 인덱스, right는 데이터 셋의 마지막 인덱스이다. 중앙값의 인덱스는 (left + right) / 2 를 통해 알아낸다.

중앙값인 30은 우리가 찾고자하는 100보다 작다. 따라서 30보다 작은 index 중 100은 절대 존재할 수 없으므로 데이터셋의 길이를 줄여준다. 100의 index는 30의index인 4보다 클 것이고, right보단 작을 것이다. 즉, left를 mid + 1로 수정하면 된다.

 

만약 우리가 찾고자 하는 값이 15라고 가정하면 중앙값인 30보다 15가 더 작으므로 15의 index는 left보다 크고, 4보다 작을 것이다. 위와 반대로 right를 mid - 1로 수정하면 된다.

 

2. left 혹은 right를 수정한 후, 위와 같은 작업을 반복한다.

mid가 가리키는 값이 target이 될 때까지 위와 같은 작업을 반복하면 된다. 앞에서 left를 수정하고 난 다음의 상태는 아래 그림과 같다.

mid가 가리키는 값이 100이므로 탐색을 종료한다.

 

코드 

private int binarySearch(int left, int right, int value) {
	while (left <= right) {
    	int mid = (left + right) / 2;
        
        if (arr[mid] < value) {
        	left = mid + 1;
        }
        else if (arr[mid] > value) {
        	right = mid - 1;
        }
        else {
        	return mid;
        }
        
    }
   
	return -1; 
}