imported>Unknown at 05:27, 7 February 2021

2021-02-07T05:27:58Z

New page

= Search =
* 컨테이너에서 값을 찾는다. 찾으면 1, 못찾으면 0을 리턴해준다.
* STL에서는 최적의 검색 기능을 자랑하는(θ(logn)) Binary Search를 제공해준다.
* Binary Search가 무엇이냐? 사람이 사전을 찾을때와 비슷하다고 보면 된다.

## 사전의 반을 펼친다.
** 만약에 내가 찾는값이 그것보다 뒤에 있으면 나머지 뒷부분의 반을 펼친다.
** 그것 보단 앞에 자료가 존재하면 처음 펼친 곳과 지금 펼친곳의 가운데를 펼친다.

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

* STL에서는 최적의 조합으로, sort + binary_search를 추천해준다. 예제를 보자.
#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]]

STL/search - Revision history

imported>Unknown at 05:27, 7 February 2021