[알고리즘] 이진 탐색(Binary Search) using vector: 22.06.09

이진 탐색(Binary Search)

검색할 범위를 절반으로 줄여가며 검색하는 방법

C++ Reference(std::binary_search)

std::binary_search - cppreference.com

---

1. 이진 탐색이란?

리스트에서 9를 이진 탐색으로 찾는 그림

• 정렬된 리스트의 중앙을 가리키는 피봇과 찾으려는 값을 비교하는 탐색법
  다음과 같은 순으로 탐색한다.
  • pivot가 주어진 리스트의 중앙을 가리키게 한다.
  • pivot과 주어진 값을 비교한다.
    • pivot보다 주어진 값이 크면, 리스트의 시작 부분을 pivot의 뒤로 옮긴다.
    • pivot보다 주어진 값이 작으면, 리스트의 끝부분을 pivot의 앞으로 옮긴다.
  • 위를 반복한다.

2. std::binary_search

template<class ForwardIt, class T>
bool binary_search(ForwardIt first, ForwardIt last, const T& value)

 

• [first, last)까지의 원소들 중에 value 값을 찾는다.
  • 반환값
    • 찾으면 true, 아니면 false를 반환한다.
• binary_search를 성공적으로 사용하려면 리스트가 반드시 일부라도(partially) 정렬되어 있어야 한다.
  또한 다음의 조건을 만족해야 한다.

---

[실습 코드]

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

/*
* ### 이진 검색
*  > 검색할 범위를 절반으로 줄여가며 검색하는 방법
*  > 정렬된 배열에서만 사용 가능
*/

template< class forwardit, class T>
bool BinarySearch(forwardit first, forwardit last, const T& value)
{
	int pivot = (last - first) / 2;

	while (first < last)
	{
		if (*(first + pivot) == value) //값이 같으면
		{
			return true; //찾음
		}
		else if (*(first + pivot) > value) //주어진 값이 더 작으면
		{
			last = first + pivot - 1; //마지막을 가운데 앞으로 이동
		}
		else if (*(first + pivot) < value) //주어진 값이 더 크면
		{
			first = first + pivot + 1; //처음을 가운데 뒤로 이동
		}

		pivot = (last - first) / 2; //가운데 다시 판별
	}

	return false;
}

int main()
{
	vector<int> vec;
	vec.push_back(1);
	vec.push_back(2);
	vec.push_back(3);
	vec.push_back(4);
	vec.push_back(5);
	vec.push_back(6);

	cout << "vec: ";
	for (vector<int>::iterator iter = vec.begin(); iter != vec.end(); ++iter)
	{
		cout << *iter;
		if (iter + 1 != vec.end())
		{
			cout << ",";
		}
	}
	cout << endl;

	cout << "Finding 2 in vec: " << std::boolalpha << BinarySearch(vec.begin(), vec.end(), 2) << endl;
	cout << "Finding 6 in vec: " << std::boolalpha << BinarySearch(vec.begin(), vec.end(), 6) << endl;
	cout << "Finding 7 in vec: " << std::boolalpha << BinarySearch(vec.begin(), vec.end(), 7) << endl;

	return 0;
}