C++ 탐색

---

<탐색>

탐색이란?

여러 개의 자료 중에서 원하는 자료를 찾는 작업이다. 컴퓨터가 가장 많이 하는 작업중의 하나로 탐색을 효율적으로 수행하여 시간을 줄이는 것은 매우 중요하다.

---

<탐색 종류>

탐색에도 정렬과 비슷하게 다양한 종류가 있으며 상황에 따라 어느 것이 효율적인지 다 다르다.

순차 탐색

-코드

int sequentialSearch(int list[], int key, int low, int high)
{
    for(int i = low; i <= high; i++)    // low부터 high까지 순차적으로 돌면서 key값을 가지면 인덱스 리턴
        if(list[i] == key)
            return i;
    return -1;	//값을 못찾으면 -1 반환
}

-장단점

장점	단점
구현이 쉽다, 정렬되지 않은 배열울 검사하는데에 유리하다	데이터가 많아지면 시간이 오래 걸린다.

-시간 복잡도

최악	평균	최적
O(n)	O(n)	O(1)

 

 

이진 탐색

-코드

int binarySearchIter(int list[], int key, int low, int high)
{
    int middle;
    while(low <= high){
        middle = (low + high) / 2;
        if(key == list[middle])    //탐색 성공시 리턴
            return middle;
        else if(key > list[middle])    //  찾고 싶은 값이 더 크면 low을 증가
            low = middle + 1;
        else    // 작으면 high감소
            high = middle - 1;
    }
    return -1;    //탐색 실패
}

-장단점

장점	단점
시간이 빠르다.	정렬 된 배열을 써야한다.

-시간 복잡도

최악	평균	최적
O(logn)	O(logn)	O(1)

 

---

<upper_bound와 lower_bound>

upper_bound는 원하는 값보다 큰 첫번째 위치의 주소(Iter)를 반환하고, lower_bound는 원하는 값이상인 수가 처음 나오는 위치의 주소를 반환한다.

 

이 함수들은 이분탐색을 기반으로 구현되었고, 알고리즘 헤더파일에 있다.

#include <algoruthm>

 

---

<upper_bound와 lower_bound 사용법>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int findVal = 3;
	int arr[6] = { 0,1,2,3,4,5 };
	vector<int> vt = { 0,1,2,3,4,5 };
	cout << lower_bound(arr,arr + 6, findVal) - arr << endl;
	cout << lower_bound(vt.begin(), vt.end(), findVal) - vt.begin() << endl;
	cout << upper_bound(arr,arr + 6, findVal) - arr << endl;
	cout << upper_bound(vt.begin(), vt.end(), findVal) - vt.begin() << endl;
}

 

 

위 예시처럼 배열에 주소를 매개변수로 적어 사용할 수 있다.

---

<upper_bound와 lower_bound 구현해보기>

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


vector<int> v = { 0, 1, 2, 3, 4, 5, 7, 8 };
int lower_bound(int key)
{
	int left = 0, right = v.size(), mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (v[mid] >= key) // 특정 조건(key값 이상) 만족
			right = mid - 1; // 특정 조건을 만족하는 작은 값 찾기 
		else
			left = mid + 1;		// 더 큰 값 중에서 만족하는 값 찾으러 가기 
	}
	return left;
}

int upper_bound(int key)
{
	int left = 0, right = v.size(), mid;
		while (left <= right)
		{
			mid = (left + right) / 2;
			if (v[mid] > key)
				right = mid - 1;
			else
				left = mid + 1;
		}
   
}

int main()
{
	int num;
    cin >> num;
	cout << lower_bound(num) << endl; // 7넣으면 6, 6넣으면 6
	cout << upper_bound(num) << endl; // 7넣으면 7, 6넣으면 6 
	return left;
}