완전탐색/이분탐색

탐색이란

탐색이란, 많은 데이터 속에서 원하는 데이터를 찾는 행위이다.

탐색의 종류

완전탐색, 이분탐색, 깊이우선탐색, 너비우선탐색, 문자열탐색, KMP, BM

 

완전탐색

모든 경우의 수를 다 해보는 방법

효율성 관점에선 최악의 방법이나 무조건 원하는 값을 탐색할 수 있다는 장점이 있음

 

종류 

- Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법

- 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT)

- BFS(너비우선탐색), DFS(깊이우선탐색)

- 재귀함수

- 순열

 

int Search(int[] arr, int n, int x)
{
 for(int i=0; i<n; ++i)
 {
  if(arr[i] == x)
  return i;
 }
  return -1;
}

 

 

 

이분탐색

이진검색이라고도 표현하며, 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘

중간값을 선택하여 타겟 값과의 대소를 비교하는 과정을 반복 Search 방법

데이터의 삽입이나 삭제가 빈번할 시에는 적합 x, 주로 고정된 데이터에 대한 탐색에 적합

int binarySearch(int key, int low, int high) {
	int mid;

	while(low <= high) {
		mid = (low + high) / 2;

		if(key == arr[mid]) {
			return mid;
		} else if(key < arr[mid]) {
			high = mid - 1;
		} else {
			low = mid + 1;
		}
	}

	return -1; // 탐색 실패 
}