이원탐색(left, right, mid) + 순환 이원탐색

*자주하는 실수
cout이나 cin 같은 거 쓸 때 맨 위에다가 이거 넣는 거 잊지 말자!!
#include <iostream>
using namespace std;

if 다음에 (조건문) 조건문은 괄호로 감싸주자!!

이원탐색

#include <iostream>
using namespace std;

int BinarySearch(int* a, const int x, const int n) {
	int left = 0; int right = n - 1;
	while (left <= right) {
		int middle = (left + right) / 2;
		if (x < a[middle]) right = middle - 1;//범위를 좁혀 왼쪽으로 간다.
		else if (x > a[middle]) left = middle + 1;
		else return middle;//찾았다.
	} 
	//없다
	return -1;
}

int main() {
	int List[] = { 1,2,3,4,5,7,9,10 };
	cout << BinarySearch(List, 3, 8) << endl;
	cout << BinarySearch(List, 5, 8) << endl;
	cout << BinarySearch(List, 11, 8) << endl;
}

순환 이원탐색

-return값에 BinarySearch가 또 들어가는 것만 다름

#include <iostream>
using namespace std;

int BinarySearch(int* a, const int x, const int left, const int right) {
	//정렬된 배열 a[0],...,a[n-1]에서 x를 탐색한다.
	if (left <= right) {
		int middle = (left + right) / 2;
		if (x < a[middle]) { return BinarySearch(a, x, left, middle - 1); }
		else if (x > a[middle]) { return BinarySearch(a, x, middle + 1, right); }
		return middle;
	}
	return -1;
}


int main() {
	int List[] = { 1,2,3,4,5,7,9,10 };
	cout << BinarySearch(List, 3, 0, 8) << endl;
	cout << BinarySearch(List, 5, 0, 8) << endl;
	cout << BinarySearch(List, 11,0, 8) << endl;
}