탐색1 : 선형탐색, 이진탐색

탐색의 분류

1. 선형 자료구조 ( 어레이, 리스트, ...) 내에서의 탐색

• 선형탐색 (linear search) 또는 순차탐색 (sequential search) 
• 이분탐색 (binary search) : 분할정복을 이용한 탐색
• 해싱 (hashing)

 

2. 비선형 자료구조 ( 트리, 그래프, ...) 내에서의 탐색

• tree traversal
• DFS
• BFS

 

선형탐색, linear Search

• 정의 : 데이터의 집합을 처음부터 끝까지 차례대로 하나씩 검색하는 방법
• 장점 : 구현하기 쉽고 데이터 집합이 정렬되어 있지 않아도 된다
• 단점 : 검색시간이 오래걸린다
• 시간복잡도
  • worst : O(n)
  • average : O(n)
  • best : O(1)     // 첫번째 인덱스의 값이 찾고자 하는 값인 경우
• 예시코드

// linear search

#include <iostream>
#include <vector>
#define MAX_SIZE 15
using namespace std;

int linearSearch(vector<int>& arr, int find);

int main() {
	vector<int> arr;

	for (int i = 0; i < MAX_SIZE; i++)
		arr.push_back((i + 1));

	cout << linearSearch(arr, 7) << endl;	// 7값의 인덱스 출력

	return 0;
}

int linearSearch(vector<int>& arr, int find) {
	int res = -1;
	for (int j = 0; j < arr.size(); j++) {
		if (arr[j] == find) {
			res = j;
			break;
		}
	}
	return res;
}

 

 

이분탐색, Binary Search

• 정의 : 데이터 집합의 범위를 반씩 나누어 가면서 분할정복하여 탐색하는 방법
• 장점 : 탐색 속도가 빠르다
• 단점 : 데이터집합 안의 값들이 정렬되어 있어야 한다.
• 시간복잡도 
  • worst : O(logn)
  • average : O(logn)
  • best : O(1)      // 중간 인덱스의 값이 찾고자 하는 값인 경우
• 예시코드

// binary search

#include <iostream>
#include <vector>
#define MAX_SIZE 15
using namespace std;

int binarySearch(vector<int>& arr, int find);

int main() {
	vector<int> arr;

	for (int i = 0; i < MAX_SIZE; i++)
		arr.push_back((i + 1));

	cout << binarySearch(arr, 7) << endl;	// 7값의 인덱스 출력

	return 0;
}

int binarySearch(vector<int>& arr, int find) {
	int res = -1;
	int left = 0;
	int right = arr.size() - 1;
	int mid;

	while (left <= right) {
		mid = left + (right - left) / 2;	// 오버플로우를 방지한 (left+right)/2 연산
		if (arr[mid] == find) {
			res = mid;
			break;
		}
		else if (arr[mid] < find) {
			left = mid+1;
		}
		else { // arr[mid] > find
			right = mid-1;
		}
	}
	return res;
}