<C++> 13. 탐색

탐색

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

이진 탐색

순차 탐색(sequential search)

• 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법
• 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사
• 평균 비교 횟수
  • 탐색 성공: (n + 1)/2번 비교
  • 탐색 실패: n번 비교

순차 탐색 알고리즘

int sequentialSearch(int list[], int key, int low, int high)
{
	for(int i=low; i<=high; i++)
	if( list[i] == key )
		return i;

	return –1;
}

 

• 시간 복잡도: O(n)
• 열거형은 식별자를 값으로 저장할 수 있는 형
• 열거형 선언 : enum 열거형명 {식별자 1, 식별자 2, 식별자 3, 식별자 4 };
  - 식별자 1부터 4까지 0에서 3까지 정수 값을 각각 나타내는 상수로 만듦
• 열거형 변수의 선언 : 열거형명 열거변수명;
• 열거형 변수에는 열거자들의 값만 대입할 수 있음
• 열거자들을 상수로 관리 -> 열거자들 가느이 산술연산 적용 안됨

enum을 사용하면 코드의 가독성을 높일 수 있음.

이진 탐색(binary search)

• 정렬된 배열의 탐색에 적합
      배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이
      왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어
      탐색의 범위를 반으로 줄여가며 탐색 진행
• (예) 10억 명중에서 특정한 이름 탐색
    • 이진탐색 : 단지 30번의 비교 필요
    • 순차 탐색 : 평균 5억 번의 비교 필요

이진 탐색 구현

int binarySearch (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 = middle+1;
		else
			high = middle-1;

	}
	return –1; // 탐색 실패
}

 

이진 탐색 vs 순차 탐색

나이 맞추기

#include <iostream>
#include <vector>
using namespace std;
void binarySearch(vector<int>& age);

int main()
{
	vector<int> age;
	int min, max;
	cout << "나이의 최솟값, 최댓값 입력 : ";
	cin >> min >> max;
	for (int i = 0; i <= max; i++)
	{
		age.push_back(i);
	}
	cout << "나이가 맞다면 YES, 더 많으면 UP, 더 적으면 DOWN을 입력하세요." << endl;
	binarySearch(age);
}

void binarySearch(vector<int>& age)
{
	string answer;
	int left = 0, right = age.size() - 1, mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		cout << age[mid] << "살입니까? : ";
		cin >> answer;
		if (answer == "YES")
		{
			cout << "맞췄다!!";
			return;
		}
		else if (answer == "DOWN")
		{
			right = mid - 1;
		}
		else if (answer == "UP")
		{
			left = mid + 1;
		}
	}
	cout << "거짓말 하셨죠?" << endl;
}