이진 탐색 (Binary Search)

log(n)의 시간 복잡도.(단계별로 n개에서 반씩 줄여가면서 하니까)

int BinarySearch(int* arr, int n, int x) // 이진 탐색
{
	int left = 0;
	int right = n - 1;

	while (left <= right)
	{
		PrintHelper(arr, n, left, right);

		int middle = (left + right) / 2; // 정수 나누기 (버림)

		cout << "middle " << middle << endl;

		if (arr[middle] > x)
		{
			right = middle - 1;
			cout << "right " << right << endl;
		}
		else if (arr[middle] < x)
		{
			left = middle + 1;
			cout << "left " << left << endl;
		}
		else
		{
			cout << "Found " << middle << endl;
			return middle;
		}
	}

	cout << "Not found" << endl;
	return -1; // Not found
}