이분 탐색(binary search)

 

이분 탐색 : 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법으로 찾으려는 데이터와 중간 위치에 있는
데이터를 반복적으로 비교하여 원하는 결과를 도출해냄.

 

 

 

배열 내 데이터들이 정렬되어 있어야 사용할 수 있는 알고리즘이며, 입력 데이터가 많거나, 탐색 범위가 넓은 편.

시간복잡도: O(logN)
확인할 때마다 원소의 개수가 절반씩 줄어듦으로써 시간 복잡도는 logN에 비례하는 시간임.

 

#include <iostream>

using namespace std;

int binary_search(int arr[], int length, int target) { // 반복적 
	int start = 0;
	int end = length-1;
	int mid;
	
	while(start<=end) {
		mid = (start+end)/2;
		if(arr[mid] == target) {
			return mid;
		} else {
			if(arr[mid] > target) {
				end = mid-1;
			} else {
				start = mid+1;
			}
		}
	}
	return -1;
}

int recursive_search(int arr[], int start, int end, int target) { // 재귀적 
	int mid = (start+end)/2;
    
	if(start>end) {
		return -1;
	}
    
	else {
		if(arr[mid]==target) {
			return mid;
		} else if(arr[mid]>target) {
			recursive_search(arr, start, mid-1, target);
		} else {
			recursive_search(arr, mid+1, end, target);	
		}
	}
} 

int main()
{							
	int search_arr[10] = {5, 9, 11, 17, 29, 30, 42, 43, 59, 101};
	int num, result, size = sizeof(search_arr) / sizeof(search_arr[0]);
	cin>>num;
	
	// result = binary_search(search_arr, size, num);
	result = recursive_search(search_arr, 0, size-1, num);
	if(result == -1) {
		cout<<"이진 탐색 실패"<<endl;
	} else {
		cout<<"데이터의 위치는 "<<result+1<<"번째에 있습니다."<<endl;
	}
	return 0;
}

 

[이분 탐색으로 해결할 수 없는 경우는?]

 

삼분 탐색(ternary search)

• 이분 탐색은 단조 증가/감소 문제에만 해당되지만 좀 더 넓은 범위의 문제를 풀때 사용가능함
• 볼록함수에서 극값 혹은 최대/최솟값을 찾을 때 사용