알고리즘(C++) / 이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound()

이진 탐색(이분 탐색) - binary_search(), lower_bound(), upper_bound()

• 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 리스트가 반드시 정렬되어 있어야 사용이 가능하다.
• start, end, mid를 사용하여 찾으려는 데이터와 mid에 있는 데이터를 반복적으로 비교하여 데이터를 찾는다.
• 전부를 탐색하는 탐색 속도에 비해 빠르다.
• 알고리즘 헤더를 선언하여 이진 탐색 함수 binary_search(), lower_bound(), uppwer_bound() 함수를 사용할 수 있다. (#include <algorithm>)
• 시간 복잡도는 O(logN)이다. 

 

함수를 알아보도록 한다.

binary_search()

찾으려는 데이터 값의 존재 여부를 알 수 있는 함수이다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
	if (binary_search(arr, arr + 10, 3)) {
		cout << "3 존재\n";
	}
	else {
		cout << "3 존재하지 않음\n";
	}
	
	if (binary_search(arr, arr + 10, 10)) {
		cout << "10 존재\n";
	}
	else {
		cout << "10 존재하지 않음\n";
	}

	return 0;
}

결과

binary_search(시작, 끝, 찾을 데이터); //이분 탐색

binary_search() 함수는 찾을 데이터가 존재한다면 true, 존재하지 않으면 false를 return 한다. 

 

lower_bound()

찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾는다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int arr[10] = { 0, 1, 1, 2, 2, 4, 4, 5, 5, 6 };

	auto it2 = lower_bound(arr, arr + 10, 2);
	cout << "location : "<< it2 - arr << "\n"; // 출력 : 3
	cout << "num : " << arr[it2 - arr] << "\n"; // 출력 : 2

	auto it3 = lower_bound(arr, arr + 10, 3);
	cout << "location : " << it3 - arr << "\n"; // 출력: 5
	cout << "num : " << arr[it3 - arr] << "\n"; // 출력: 4

	return 0;
}

결과

찾으려는 key값 2의 첫 번째 위치를 반환한다. 

찾으려는 key값 3은 존재하지 않으므로 3보다 큰 수의 첫번째 위치를 반환한다. 

 

upper_bound()

찾으려는 key 값보다 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾는다.

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int arr[10] = { 0, 1, 1, 2, 2, 4, 4, 5, 5, 6 };

	auto it2 = upper_bound(arr, arr + 10, 2);
	cout << "location : " << it2 - arr << "\n"; // 출력 : 5
	cout << "num : " << arr[it2 - arr] << "\n"; // 출력 : 4

	auto it3 = upper_bound(arr, arr + 10, 3);
	cout << "location : " << it3 - arr << "\n"; // 출력 : 5
	cout << "num : " << arr[it3 - arr] << "\n"; // 출력 : 4

	return 0;
}

결과