1. 이진 탐색

1. 데이터가 정렬된 상태로 있어야지만 이진 탐색이 가능하다.

2. 정렬된 연결 리스트로는 이진탐색 불가능함 (Random Access X)

2. 코드

void B(int v)
{
	int left = 0;
	int right = vec.size() - 1;

	int count = 0;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		
		cout << "수행 횟수 : " << count << endl;
		cout << "범위 : " << left << "~" << right << endl;
		
		if (v < vec[mid])
		{
			right = mid - 1;
		}
		else if (v > vec[mid])
		{
			left = mid + 1;
		}
		else
		{
			cout << "find : " << v << endl;
			break;
		}
		
		++count;
	}
}

이런식으로 절반식 줄여가면서 O(log n)으로 탐색을 한다.

핵심은 v < vec[mid] 일경우 right = mid - 1 만 변경한다는 점이다.