[ C++ ] Binary search 구현해보기.

전제조건 🤔

검색하고자 하는 대상(어레이 형태의 데이터 타입)이 오름 또는 내림차순의 정렬된 상태여야 한다.

알고리즘 개념. 🙏🔗

• 노마드코더 유튜브 : 알고리즘(바이너리 서치) 

• 위키피디아 : https://en.wikipedia.org/wiki/Binary_search_algorithm

Binary search algorithm - Wikipedia

 

알고리즘의 단계 🤤

1. 어레이를 오름차순 또는 내림차순으로 정렬한다
2. 어레이의 절반 위치 요소를 선택
3. 찾을 타겟 값과 절반 위치 요소를 비교
4. 크고, 작음에 따라서 다음 탐색 위치 범위를 정의(범위를 이전 범위의 절반 씩 줄여나감.)
5. 위의 과정을 반복.(~타겟 값을 찾을 때까지)

바이너리 서치 개념.

 

CODE 💻

1. 어레이를 오름차순 또는 내림차순으로 정렬한다

처음부터 정렬된 정수 타입 벡터를 선언했습니다.

vector<int> vec = { 2,3,4,5,6,7,10,13,20,22,23,29,31 };

 

 

2. 어레이의 절반 위치 요소를 선택

int minIdx = 0;
int maxIdx = vec.size() - 1;
// 벡터의 절반 위치 인덱스를 복사
int n = (minIdx + maxIdx) / 2;

 

 

추가로, 탐색 대상의 Iteration number를 정의 후, 그 횟수를 기준으로 루프를 돌려준다.

바이너리 서치는 어레이 크기의 제곱근만큼만 루프를 돌려주면 되는 것 같다.

(trial and error를 통해 알아낸 사실입니다. 다를 수 있으니, 적용할 때 검토해보세요.)

그래서, Iteration number를 다음과 같이 정의한다.

int numIter = sqrt(vec.size());

 

3. 찾을 타겟 값과 절반 위치 요소를 비교

아래 코드는 while 루프 내에서 수행된다.

비교 결과에 따라서, 최대/최소 인덱스를 업데이트해준다.  

while(i < numIter){
...
if (target > vec[n]) {
	minIdx = n;
}
else if (target < vec[n]) {
	maxIdx = n;
}
else if (target == vec[n]) {
	break;
}
...

 

4. 크고, 작음에 따라서 다음 탐색 위치 범위를 정의

3에서 정의한 각 minIdx, maxIdx 변수에 따라 다음 루프의 범위가 업데이트된다.

// updatd n, i
n = (minIdx + maxIdx) / 2;
i++;
// while loop end...
}

 

전체 코드 ⚙️

int main() {

	vector<int> vec = { 2,3,4,5,6,7,10,13,20,22,23,29,31 };

	int target = 29;
	int targetIdx = 0;
	cout << "target number : " << target << endl;

	int minIdx = 0;
	int maxIdx = vec.size() - 1;
	
	int numIter = sqrt(vec.size());

	int n = (minIdx + maxIdx) / 2;
	int i = 0;

	while (i < numIter)
	{
		if (target > vec[n]) {
			minIdx = n;
		}
		else if (target < vec[n]) {
			maxIdx = n;
		}
		else if (target == vec[n]) {
			break;
		}

		// updatd n, i
		n = (minIdx + maxIdx) / 2;
		i++;

	}

	targetIdx = n;
	cout << "the closest index of array is ... " << targetIdx << endl;

	return 0;
}