1. 이분탐색

이분탐색은 숫자 UP DOWN 게임과 같다. 정렬된 데이터에서 탐색 범위의 가운데 값을 확인하고 탐색 범위를 절반씩 좁혀가며 target data를 찾아내는 방식이다.

• 이진 탐색을 수행하기 위해서는 범위의 시작점을 가리키는 변수 (start), 범위의 끝점을 가리키는 변수(end), 가운데 값을 가리키는 변수 (mid = (start + end) / 2) 세 개가 필요하다.

2. 코드 구현 (C++)

int binarySearch(int target)
{
	int st = 0; //시작점
	int en = n - 1; //끝점
	int mid;
	while (st <= en)
	{
		mid = (st + en) / 2;
		if (arr[mid] < target)
		{
			st = mid + 1;
		}
		else if (arr[mid] > target)
		{
			en = mid - 1;
		}
		else return 1; //target이 있다면 1 리턴
	}
	return 0; //target이 없다면 0 리턴
}
int n = 20;
int arr[20];
int main(void)
{	
	int target = 12;
	for (int i = 0; i < n; i++)
	{
		arr[i] = (i + 1);
	} //1부터 20까지 수를 넣음

	binarySearch(target);
}

3. 코드 구현 (C++, STL)

int n = 20;
int arr[20];
int main(void)
{
	int target = 12;
	for (int i = 0; i < n; i++)
	{
		arr[i] = (i + 1);
	} //1부터 20까지 수를 넣음

	binary_search(arr, arr + 20, target);
}