이진 탐색

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 알고리즘입니다. 탐색을 시작할 때는 배열의 중간값을 찾아서 찾고자 하는 값과 비교합니다. 만약 찾고자 하는 값이 중간값보다 작으면 중간값 왼쪽 부분 배열에서 탐색을 계속하고, 찾고자 하는 값이 중간값보다 크면 중간값 오른쪽 부분 배열에서 탐색을 계속합니다. 이런 과정을 반복해서 값을 찾아냅니다.

이진 탐색의 시간 복잡도는 O(log n)입니다. 이는 배열의 크기가 2배로 증가할 때마다 한 번씩만 비교하면 되기 때문입니다. 이진 탐색은 배열이 정렬되어 있어야만 사용할 수 있습니다.

아래는 C++로 이진 탐색을 구현한 예시입니다.

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

int binarySearch(int arr[], int n, int x) {
	sort(arr, arr + n);

	int left = 0, right = n - 1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (arr[mid] == x) {
			return mid;
		}
		if (arr[mid] < x) {
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return -1; // 값이 없으면 -1을 반환
}

void main() {
	int a[] = { 1,3,5,4,6,9,2 };
	int n = size(a);

	cout << binarySearch(a, n, 2) << endl;
}

위의 코드에서 arr은 정렬된 배열, n은 배열의 크기, x는 찾고자 하는 값입니다. left와 right는 탐색 범위의 시작과 끝 인덱스를 나타냅니다. mid는 left와 right의 중간값을 나타냅니다. arr[mid]와 x를 비교해서 찾고자 하는 값이 mid보다 작으면 왼쪽 부분 배열에서 탐색을 계속하고, 크면 오른쪽 부분 배열에서 탐색을 계속합니다. 찾고자 하는 값이 없으면 -1을 반환합니다.