[알고리즘]이진 탐색 Binary Search 알고리즘

[ 선형 탐색 Linear Search ]

 

 선형 탐색은 배열의 첫 번째 원소부터 차례대로 전체 원소를 방문하면서 해당 원소가 검색하려는 원소와 같은지 확인하는 방법입니다. 

 

 이 방법의 장점은 입력 시퀀스의 정렬 여부와 상관없이 항상 잘 동작한다는 점입니다. 

 

 하지만 이 방법은 효율적이지 않으며, 주어진 배열이 정렬되어 있어도 그 점을 전혀 활용하지 못합니다. 

 

 선형 탐색 알고리즘의 시간 복잡도는 O(N)입니다. 

 

int linear_search(int N, vector<int> arr) {
	for(int i = 0; i < arr.size(); i++){
    		if(arr[i] == N)
        		return i;
    	}
    return -1;
}

 

 

 

 

[ 이진 탐색 Binary Search ]

 

 선형 탐색과 달리 이진 탐색은 정렬된 배열에서만 동작하는 알고리즘으로, 분할 정복 (divide & conquer) 알고리즘이라고 할 수 있습니다. 

 

 배열의 중간 원소와 검색하려는 원소를 비교하여 배열을 분할함으로써 검색을 수행합니다. 

 

 이진 탐색의 시간 복잡도는 O(log N) 입니다. 

 

 

int binary_search (vector<int> arr, int s, int e, int x) {
	if (s == e)
    		return (arr[s] == x) ? s : -1;

	int mid = (s + e) / 2;
    	if (x == arr[mid])
    		return mid;
    	else if (arr[mid] > x)
    		return binary_search(arr, s, mid-1, x);
    	else 
    		return binary_search(arr, mid+1, e, x);
}

 

예시)

 

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

int x = 2

 

 

1. 현재 arr의 가운데 원소와 x를 비교한다.

 

int mid = (0 + 9) / 2 = 4

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]	arr[9]
1	2	3	4	5	6	7	8	9	10

 

 2. 만약 두 원소가 같다면 x를 찾은 것이므로 검색을 중단한다. 

 

 3. 그렇지 않다면 다음 두 규칙에 따라 검색을 진행한다. 

• 만약 중간원소가 x보다 크다면 중간원소보다 작은 원소들에 대해 검색 진행
• 만약 중간원소가 x보다 작다면 중간원소보다 큰 원소들에 대해 검색 진행

int mid = (0 + 3) / 2 = 1

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]	arr[6]	arr[7]	arr[8]	arr[9]
1	2	3	4	5	6	7	8	9	10