C++에서 이진 검색 구현
이 기사에서는 C++에서 이진 검색 알고리즘을 구현하는 방법을 설명합니다.
C++에서std::vector컨테이너에 대한 이진 검색 알고리즘 구현
검색 알고리즘은 가장 일반적인 문제에서 사용되는 기본 서브 루틴이며 가장 효율적인 방법으로 실행하는 것이 중요합니다. 다양한 유형의 검색 알고리즘이 있습니다. 일부는 특수 데이터 구조에 맞게 조정되고 일부는 더 일반적으로 적용될 수 있습니다.
이진 검색은 정렬 된 키 배열에서 사용해야하는 분할 및 정복 유형 알고리즘입니다. 최악의 경우 성능 때문에 종종 로그 검색이라고 불리며이 기사의 뒷부분에서 살펴볼 것입니다.
이진 검색을 다음과 같이 설명 할 수 있습니다.k키를 찾아야하는 정렬 된 객체 배열이 있으면 주어진 키를 배열의 중간 요소와 비교해야합니다. 키가 요소보다 작 으면 배열의 왼쪽 절반에 위치해야합니다. 키가 더 크면 오른쪽 절반에서 찾아야합니다.
이 조회 프로세스를 각각의 작은 절반 배열에서 반복적으로 반복하면 결국 키의 위치를 찾거나 키가 배열에 없음을 나타냅니다. 알고리즘을 자연 재귀 적이라고 설명하더라도 반복적 방법을 사용하여 구현할 수 있지만 재귀 적 방법에 중점을 둘 것입니다.
다음 예제 코드는[1-1000]범위에서 천 개의 임의의 정수를 생성하여std::vector컨테이너에 저장합니다. 그런 다음std::sort알고리즘을 사용하여 벡터를 정렬하고 검색 할 9 개의 정수로 구성된 또 다른 벡터를 선언합니다. searchVector래퍼 함수는 재귀 함수binarySearch를 호출하는 데 사용됩니다.
후자는 두 위치 인덱스의 첫 번째 인덱스가 다른 인덱스보다 큰지 확인합니다. 그렇다면 함수가 반환됩니다. 반환 값-1은 주어진 키에 대해 찾을 수 없음 상태를 나타내는 데 사용됩니다. 다음으로 중간 위치가 계산되고 키와 비교되며 참이면 인덱스 값을 반환합니다. 마지막으로 배열에서 검색해야 할 부분을 선택하고 해당 인덱스를 사용하여 동일한 함수를 호출합니다.
#include <iostream>
#include <random>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;
template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
if (s1 > s2) return -1;
auto middle = (s1 + s2) / 2;
if (item == vec.at(middle)) return middle;
if (item > vec.at(middle))
return binarySearch(vec, item, middle + 1, s2);
else
return binarySearch(vec, item, s1, middle - 1);
}
template <typename T>
int searchVector(const vector<T> &vec, T &item) {
return binarySearch(vec, item, 0, vec.size() - 1);
}
int main() {
std::random_device rd;
std::default_random_engine eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
std::vector<int> vec;
vec.reserve(NUMS_TO_GEN);
for (int n = 0; n < NUMS_TO_GEN; ++n) {
vec.push_back(distr(eng));
}
std::sort(vec.begin(), vec.end());
std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
for (auto &item : vec2) {
searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
}
cout << endl;
return EXIT_SUCCESS;
}
출력:
did not, found, found, did not, found, did not, found, did not, found,
이진 검색 알고리즘의 복잡성 분석
이진 검색에는O(log n)복잡성이 있으므로 별칭 이름 - 로그 검색입니다. 반복 비용을 분석하여 반복 알고리즘 구현의 실행 시간을 대략적으로 추정 할 수 있습니다. 중간 요소를 찾는 것은 일정한 시간 작업이며 배열의 절반을 탐색해야합니다.
다음 프로그램에서는 STL std::sort알고리즘을 사용하여 바이너리 검색 기능에 대한 검증 테스트를 시연합니다. 그러나이 검사는 공식적인 검증이 아니며 코드 동작을 디버그하고 분석하기 위해 알고리즘 구현 프로세스 중에 빠른 테스트 사례를 제공 할뿐입니다.
#include <iostream>
#include <random>
#include <vector>
using std::cout;
using std::endl;
using std::vector;
constexpr int MIN = 1;
constexpr int MAX = 1000;
constexpr int NUMS_TO_GEN = 1000;
template <typename T>
int binarySearch(const vector<T> &vec, T &item, int s1, int s2) {
if (s1 > s2) return -1;
auto middle = (s1 + s2) / 2;
if (item == vec.at(middle)) return middle;
if (item > vec.at(middle))
return binarySearch(vec, item, middle + 1, s2);
else
return binarySearch(vec, item, s1, middle - 1);
}
template <typename T>
int searchVector(const vector<T> &vec, T &item) {
return binarySearch(vec, item, 0, vec.size() - 1);
}
int main() {
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
std::vector<int> vec;
vec.reserve(NUMS_TO_GEN);
for (int n = 0; n < NUMS_TO_GEN; ++n) {
vec.push_back(distr(eng));
}
std::sort(vec.begin(), vec.end());
std::vector<int> vec2{2, 111, 222, 5, 333, 7, 8, 444, 100};
for (auto &item : vec2) {
searchVector(vec, item) != -1 ? cout << "found, " : cout << "did not, ";
}
cout << endl;
for (auto &item : vec2) {
std::find(vec.begin(), vec.end(), item) != vec.end() ? cout << "found, "
: cout << "did not, ";
}
return EXIT_SUCCESS;
}
출력:
found, found, found, found, did not, did not, found, found, found,
found, found, found, found, did not, did not, found, found, found,
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook