[ALGORITHM] 22. 이진 탐색

이진 탐색(Binary Search)은 탐색 범위를 반으로 나누어 원하는 값을 찾아내는 알고리즘이다.

주로 정렬된 배열 또는 리스트에서 사용되며, 원하는 값과 중간 위치의 값을 비교해 탐색 범위를 계속해서

반으로 나누어 가면서 목푯값을 찾아낸다. 분할 정복(divide and conquer) 기법을 기반으로 하며,

각 단계에서 탐색 범위를 반으로 줄여나가기 때문에 효율적인 알고리즘 중 하나이다.

 

template <typename T>
bool binary_search(const std::vector<T>& data, T target) {

	int lower = 0;
	int upper = data.size() - 1;

	while (lower <= upper) {

		int mid = (lower + upper) / 2;

		if (data[mid] == target) {

			return true;
		
		} else if (data[mid] < target) {

			lower = mid + 1;
		
		} else {

			upper = mid - 1;
		}
	}

	return false;
}

 

 

특징

 

1. 정렬된 데이터에 적합 : 정렬된 데이터에 효과적으로 사용할 수 있으며

정렬되어 있지 않은 데이터에서는 선형 탐색이 더 적합하다.

2. 분할 정복 : 주어진 데이터를 반으로 나누어 탐색 범위를 좁혀나가는 분할 정복 방식을 사용하기에

탐색 범위를 빠르게 줄일 수 있다.

3. 시간 복잡도 : 정렬된 데이터에서 탐색을 수행하므로 시간 복잡도가 O(log n)이다.

 

 

장점

 

1. 빠른 속도 : 각 단계에서 탐색 범위를 반으로 줄이기 때문에 선형 탐색에 비해 훨씬 빠르다.

2. 정확한 위치 반환 : 찾고자 하는 값이 데이터에 존재하는 경우 정확한 위치를 반환한다.

 

 

단점

 

1. 정렬된 데이터가 필요 : 정렬된 데이터에서만 동작하기에 데이터가 정렬되어 있지 않은 경우에는 사용할 수 없다.

2. 추가 메모리 사용 : 재귀적인 방식으로 구현할 경우에는 호출 스택에 대한 추가 메모리가 필요할 수 있으며,

반복문을 사용하면 이를 회피할 수 있다.

3. 삽입, 삭제 시 복잡도가 높음 : 데이터를 삽입하거나 삭제할 때는 배열이 정렬된 상태를 유지해야 하므로

추가적인 작업이 필요하다.