[C++] 이진탐색 binary_search, upper_bound, lower_bound 함수 사용법

C++로 코딩을 하다가 이진탐색을 할 필요가 있다면 직접 구현할 필요없이 <algorithm> 헤더에 정의되어 있는 binary_search() 함수를 사용하면 된다. C++에서 이진탐색을 어떻게 하는지 알아보자.

 

일단 이진탐색이라는 것은 데이터가 정렬되어 있다는 전제하에 가능하다.

정렬을 하려면 sort() 함수를 이용하면 된다.

정렬을 설명하기엔 너무 길어질 것 같으니 sort() 함수 사용법은 이전 포스팅을 참고하면 된다.(↓링크)

https://breakcoding.tistory.com/117?category=876361

[C++] vector (벡터) 정렬, 배열 정렬하기

binary_search 함수의 사용법은 간단하다.

http://www.cplusplus.com/reference/algorithm/binary_search/

binary_search - C++ Reference

binary_search() 함수의 첫 번째, 두 번째 인자는 내가 어디에서 찾고 싶은지 (배열이든 벡터든) 그 자료구조의 시작 주소와 끝나는 주소를 넣어주면 된다. 주의해야 할 것은 주소를 넣어줘야 한다는 것이다.

찾고 싶은 곳이 크기가 6인 arr라는 배열이라면 arr를 첫 번째 인자로, arr+6을 두 번째 인자로 넣어주면 된다.

찾고 싶은 곳이 v라는 벡터라면 v.begin()을 첫 번째 인자로, v.end()를 두 번째 인자로 넣어주면 된다.

세 번째 인자는 그 곳에 있는지 없는지 궁금한 내가 찾고 싶은 대상이다.

반환 타입은 bool 타입으로, 있으면 1(true), 없으면 0(false)를 반환한다.

 

크기가 10인 정렬된 배열 arr에 3이 있는지 없는지 알고 싶다면

bool isIn = binary_search(arr, arr + 10, 3);

정렬된 벡터 v에 3이 있는지 없는지 알고 싶다면

bool isIn = binray_search(v.begin(), v.end(), 3);

이렇게 해주면 된다.

arr 배열에 또는 v 벡터에 3이 있다면 isIn에는 true가 저장되고 3이 없다면 isIn에는 false가 저장된다.

 

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;


int main() {
	int arr[] = { 3, 16, 7, 1, 20, 8, 3, 10, 25, 18 };
	sort(arr, arr + 6); //이진탐색 전에 반드시 정렬을 해줘야 한다.
	cout << "arr에 8이 있나요? " << boolalpha << binary_search(arr, arr + 6, 8) << endl;
	cout << "arr에 2가 있나요? " << boolalpha << binary_search(arr, arr + 6, 2) << endl;
	return 0;
}

8은 배열 v에 있으니 true를, 2는 배열 arr에 없으니 false를 반환하는 것을 볼 수 있다.

 

벡터도 마찬가지이다.

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;


int main() {
	vector<int> v = { 3, 16, 7, 1, 20, 8, 3, 10, 25, 18 };
	sort(v.begin(), v.end()); //이진탐색 전에 반드시 정렬을 해줘야 한다.
	cout << "arr에 8이 있나요? " << boolalpha << binary_search(v.begin(), v.end(), 8) << endl;
	cout << "arr에 2가 있나요? " << boolalpha << binary_search(v.begin(), v.end(), 2) << endl;
	return 0;
}

 

하지만 있는지 없는지 true, false로 반환을 해줄 뿐 어느 인덱스에 있는지는 binary_search 함수로는 알 수 없다.

그래서 사용하는 것이 upper_bound, lower_bound 함수이다.

upper_bound와 lower_bound의 첫 번째, 두 번째 인자는 내가 찾고 싶은 범위를 주소로 지정해주면 된다. 꼭 배열 전체, 벡터 전체일 필요는 없다. 해당 범위를 지정해주고 그 안에 있는지만 찾고 싶으면 그렇게 지정해주면 된다. binary_search 함수의 인자와 똑같다.

세 번째 인자도 binary_search의 세 번째 인자처럼 몇 개 있는지 알고 싶은 그 대상을 적어주면 된다.

 

lower_bound 함수는 내가 찾고자 하는 그 대상이 저장된 인덱스 중 가장 작은 인덱스를 반환한다.

upper_bound 함수는 내가 찾고자 하는 그 대상이 저장된 인덱스 중 가장 큰 인덱스+1을 반환한다.

 

예를 들어 정렬된 arr 배열에 다음과 같이 저장되어 있었다고 하자.

1 3 4 4 7 10 10 10 13 17

lower_bound(arr, arr + 10, 10)을 한다면 10이 처음 등장하는 인덱스인 인덱스 5의 주소를 반환한다.

upper_bound(arr, arr + 10, 10)을 한다면 10이 마지막으로 등장하는 인덱스+1인 인덱스 8의 주소을 반환한다.

iterator(메모리 주소)를 반환하기 때문에 몇 번째 인덱스인지 알아보고 싶으면 배열이나 벡터의 시작주소를 빼보면 된다.

 

일단 lower_bound와 upper_bound 함수의 반환값을 알아보기 위해서 그냥 출력해보면

#include <iostream>
#include <algorithm>
using namespace std;


int main() {
	int arr[] = { 1, 3, 4, 4, 7, 10, 10, 10, 13, 17 };
	sort(arr, arr + 10);
	cout << "lower_bound: " << lower_bound(arr, arr + 10, 10) << endl;
	cout << "upper_bound: " << upper_bound(arr, arr + 10, 10) << endl;
	return 0;
}

이렇게 주소를 반환하는 것을 알 수 있다. 004FFBE4에서 004FFBD4를 빼면 12이다. arr가 int 타입이므로 인덱스 5의 주소와 8의 주소는 3 x 4byte 총 12바이트 차이나는 것이다.

 

이렇게 주소 말고 인덱스로 보고 싶다면 이렇게 시작주소를 빼주면 된다. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main() {
	vector<int> v = { 1, 3, 4, 4, 7, 10, 10, 10, 13, 17 };
	sort(v.begin(), v.end());
	cout << "lower_bound: " << lower_bound(v.begin(), v.end(), 10) - v.begin() << endl;
	cout << "upper_bound: " << upper_bound(v.begin(), v.end(), 10) - v.begin() << endl;
	return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;


int main() {
	int arr[] = { 1, 3, 4, 4, 7, 10, 10, 10, 13, 17 };
	sort(arr, arr + 10);
	cout << "lower_bound: " << lower_bound(arr, arr + 10, 10) - arr << endl;
	cout << "upper_bound: " << upper_bound(arr, arr + 10, 10) - arr << endl;
	return 0;
}

이렇게 10의 시작인덱스, 10의 마지막 인덱스+1을 출력하는 것을 볼 수 있다. 그 인덱스에 뭐가 들어있는지 알아보고 싶으면 역참조 연산자 *로 데이터에 접근해서 출력해보면 된다. 10의 마지막 인덱스 한 칸 뒤에는 13이 저장되어 있으니 13이 출력될 것을 알 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


int main() {
	int arr[] = { 1, 3, 4, 4, 7, 10, 10, 10, 13, 17 };
	sort(arr, arr + 10);
	cout << "lower_bound: " << *lower_bound(arr, arr + 10, 10) << endl;
	cout << "upper_bound: " << *upper_bound(arr, arr + 10, 10) << endl;
	return 0;
}

역참조 연산자가 익숙치 않다면 이전 포스팅을 참고하면 도움이 될 것이다. (↓링크)

https://breakcoding.tistory.com/81

[C++] 포인터

10이 arr에 몇 개가 있는지 알고 싶다면 upper_bound에서 lower_bound를 빼보면 된다.

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int arr[] = { 1, 3, 4, 4, 7, 10, 10, 10, 13, 17 };
	sort(arr, arr + 10);
	cout << "arr에 10은 " << upper_bound(arr, arr + 10, 10) - lower_bound(arr, arr + 10, 10) << "개가 있다" << endl;
	return 0;
}