U E D R , A S I H C RSS

STL/search

Search

  • 컨테이너에서 값을 찾는다. 찾으면 1, 못찾으면 0을 리턴해준다.
  • STL에서는 최적의 검색 기능을 자랑하는(θ(logn)) Binary Search를 제공해준다.
  • Binary Search가 무엇이냐? 사람이 사전을 찾을때와 비슷하다고 보면 된다.
    1. 사전의 반을 펼친다.
    2. 만약에 내가 찾는값이 그것보다 뒤에 있으면 나머지 뒷부분의 반을 펼친다.
    3. 그것 보단 앞에 자료가 존재하면 처음 펼친 곳과 지금 펼친곳의 가운데를 펼친다.

  • 이 과정을 재귀적으로 하면 값을 찾을수 있다. 이런 탐색 방법을 Binary Search 라고 부른다. 이것이 성립하려면, 원소들이 정렬되어 있고, 임의접근(random)이 가능해야 한다. 정렬이 안되어 2,3 번의 과정을 진생할수 없다.

  • STL에서는 최적의 조합으로, sort + binary_search를 추천해준다. 예제를 보자.

~cpp 
#include <iostream>
#include <vector>
#include <algorithm>	// search 알고리즘 쓰기 위한것

using namespace std;

int main()
{
	int ar[10] = {45,12,76,43,75,32,85,32,19,98};	

	vector<int> v(&ar[0], &ar[10]);		
	sort(v.begin(), v.end());

	if(binary_search(v.begin(), v.end(), 85))
		cout << "찾았다.";
	else 
		cout << "못찾았다.";

	return 0;
}
  • sort해준다음 binary_search()의 인자로는 시작부분, 끝부분, 찾고자 하는 원소. 이렇게 넣어주면 된다.
  • list 컨테이너와 같이 임의접근 iterator를 지원하지 않는 컨테이너에는 적용할 수 없다.
----
STL
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.0101 sec