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

이진 탐색(Binary Search)

정렬된 배열에서 특정 값을 찾는 알고리즘입니다.(필수조건!)

특징

1. 반복 또는 재귀적 구현: 이진 탐색은 반복문이나 재귀 함수를 사용하여 구현할 수 있습니다.
2. 정렬된 배열에서 사용: 이진 탐색은 정렬된 배열에서만 사용할 수 있습니다. 배열의 중간 값을 기준으로 탐색 범위를 좁혀가며 값을 찾습니다.
3. 시간 복잡도: 이진 탐색의 시간 복잡도는 O(log n)입니다. 배열을 반으로 분할하면서 탐색 범위를 절반으로 줄여나가기 때문에 탐색 시간이 로그 시간에 비례합니다.

알고리즘 동작 방식

1. 탐색 범위의 시작 인덱스와 끝 인덱스를 설정합니다.
2. 탐색 범위의 중간 인덱스를 찾습니다.
3. 중간 값과 찾고자 하는 값을 비교합니다.
   • 중간 값이 찾고자 하는 값과 일치하면 탐색 성공입니다.
   • 중간 값이 찾고자 하는 값보다 작으면 탐색 범위를 오른쪽 절반으로 좁힙니다.
   • 중간 값이 찾고자 하는 값보다 크면 탐색 범위를 왼쪽 절반으로 좁힙니다.
4. 탐색 범위를 좁혀가며 위의 과정을 반복합니다.
5. 탐색 범위가 비어있을 때까지 반복합니다. 비어있을 경우, 찾고자 하는 값은 배열에 존재하지 않는 것입니다.

장점

1. 시간 복잡도가 로그 시간에 비례하여 매우 효율적입니다. 크기가 큰 배열에서도 빠른 탐색이 가능합니다.
2. 정렬된 배열에서만 사용 가능하므로, 정렬된 데이터에서의 탐색에 유용합니다.

단점

1. 배열이 정렬되어 있어야만 사용할 수 있습니다. 정렬되지 않은 배열에서는 사용할 수 없습니다.
2. 배열이 동적으로 변경되는 경우에는 이진 탐색을 사용할 수 없습니다.
3. 추가적인 메모리 공간을 사용하지 않으므로, 이진 탐색 자체는 제자리 알고리즘이지만, 재귀적 구현 시에는 스택 메모리를 사용할 수 있습니다.

요약

이진 탐색은 정렬된 배열에서 매우 효율적으로 동작하는 탐색 알고리즘입니다.

시간 복잡도가 로그 시간에 비례하므로 크기가 큰 배열에서도 빠른 탐색이 가능합니다.

그러나 정렬된 배열에서만 사용 가능하고, 배열이 동적으로 변경되는 경우에는 사용할 수 없습니다.

https://www.doabledanny.com/binary-search-javascript

void DoBinarySearch()
{
	vector<int> arr;
	arr.assign(MAX_SIZE, int());

	int count = 0;
	for (int& num : arr)
		num = count++;

	int find = rand() % MAX_SIZE;

	cout << "Find " << find << endl;
	cout << "Index " << BinarySearch(arr, find);

	cout << endl;

	Pause;
	return;
}

int BinarySearch(vector<int> arr, int find)
{
	int left = 0;
	int right = arr.size() - 1;

	while (left <= right)
	{
		int mid = left + (right - left) / 2;
		if (arr[mid] == find) return mid;
		else if (arr[mid] < find) left = mid + 1;
		else right = mid - 1;
	}
	return -1;
}