binary search 구현 C++ (중복 가능, 값 없는 경우 포함)

알고리즘 복기용 메모

 

binary search : 정렬되어 있는 상태에서 특정 값의 위치를 찾는 검색 알고리즘

절반 위치씩 쪼개면서 검색을 하기 때문에 복잡도는 O(log N)

 

구현하고자 하는 것 : 중복 가능한 배열이 오름차순 정렬 가정

1. 찾고자 하는 값이 없을 때는 해당 값이 있다면 있어야 할 위치를 리턴

2. 찾고자 하는 값이 있고, 중복된 값이라면 가장 첫 번째 인덱스를 리턴

3. 찾고자 하는 값이 단일 값이라면 해당 인덱스를 리턴

 

중복이 없다 + 타겟이 존재한다는 기본적인 binary search의 경우, 단순히 left, right +-1 을 해주면서 target을 만나면 끝내는 식으로 진행하면 된다. 

( while(left <= right) {... left = mid + 1, ..., right = mid - 1} )

 

하지만 중복 가능 + 값 없을 수도 있음 + 값 있다면 가장 첫 번째 인덱스 리턴 이라는 조건이 좀 더 일반적이므로, 이에 대한 코드를 작성하면 아래와 같다.

 

3번 조건은 기본 binary search와 동일하므로 항상 만족한다.

 

while 내의 else 문과 같이 arr[mid] == target 이더라도 right = mid 로 계속 위치를 최대한 앞으로 움직임으로써 

중복 값 중 첫 번째 index를 만족시키도록 한다.

(종료 조건이 left == right 이므로, right 이 target 보다 앞으로 움직이더라도 결국 target의 첫 번째 위치로 돌아옴)

따라서 2번 조건을 만족하게 된다. 

 

while 내의 if 문과 같이 arr[mid] < target 인 경우, left = mid + 1 이므로,

target이 실제로 존재하지 않더라도 target이 존재한다면 있어야 할 실제 위치,

즉, target보다 작은 수 중 가장 큰 값의 마지막 index + 1 을 만족하게 된다. 

따라서 1번 조건을 만족하게 된다.

 

#include <iostream>

using namespace std;

int binary_search(int arr[], int len, int target)
{
	// arr은 오름차순 정렬 가정 
	// arr에 중복된 수 있을 수도 있고, 없을 수도 있고, 
    // target이 arr에 있을 수도, 없을 수도 있음  
	 
	// 중복 있는 경우, 가장 첫 번째 등장하는 index 리턴 
	// 중복 없는 경우, 일반적인 binary search 
	// target 없는 경우, target보다 작은 값 중 가장 큰 값의 index + 1 리턴 
    // (즉, target이 있었다면 있어야 할 index.)
	
	int left = 0;
	int right = len;
	int mid = 0;
	
	int res;
	if(arr[0] > target) {
		res = 0;
		return res;
	}
	if(arr[len - 1] < target) {
		res = len;
		return res;
	}
	
	while(left < right) {
		mid = (left + right) / 2;
		
		if(arr[mid] < target) {
			left = mid + 1;
		} 
		else {
			// 중복된 target 이어도 right = mid 로 앞으로 최대한 움직임  
			right = mid;
		}
	}
	
	res = right;
	
	return res;
}

int main()
{
	int arr[] = {1,2,2,2,2,4,6,6,7,9};
	int len = sizeof(arr) / sizeof(arr[0]);
	
	printf("idx : ");
	for(int i = 0; i < len; i++) {
		printf("%d ", i);
	}
	printf("\n");
	
	printf("arr : ");
	for(int i = 0; i < len; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	printf("target -> idx of arr \n");
	for(int i = 0; i <= 10; i++) {
		int target = i;
		printf("%d -> %d\n", target, binary_search(arr, len, target));	
	}
}