이진탐색 알고리즘(binary search)

이진탐색 알고리즘은 기본적으로 O(log n)의 시간복잡도를 가진다.

O(1) (constant time complexity) 다음 가장 빠른 시간복잡도가 O(log n)이기 때문에,

상당히 빠른 알고리즘에 속한다. 그리고 아무리 생각해도 정말 효율적이다.

10개의 숫자가 정렬이 되어있다고 가정해보자.

 

10 20 30 40 50 60 70 80 90 100 

 

여기서 30의 숫자를 찾으려고 한다면,

이진탐색 알고리즘으로 처음에 중간 값인 50을 비교하고 30은 50보다 작기 때문에 

50의 오른쪽 부분은 더 이상 볼 필요가 없어진다.

이제 끝점을 초기의 중간 값의 왼쪽으로 한 칸 옮긴다.

10 20 30 40 

이제 중간 값이 20이 된다. 

30은 20 보다 커서, 10과 20이 필요 없어진다.

30과 40이 남고 이제 중간 값인 30 = 30 이 되어서

총 3번의 Step만으로 목표로 하는 숫자를 찾았다.

 

C++로 작성된 이진 탐색 소스코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

// 벡터 레퍼런스를 넘겨줘야한다. 
// 앰퍼샌드를 빼면, 그대로 Copy하기 때문에 시간복잡도가 O(n)이 된다.
int binarySearch(vector<int> &arr, int target, int start, int end)
{
	while (start<=end)
    {
    	int mid = (start+end)/2;
        if (arr[mid] == target) return mid;
        // 찾는 target이 중간값보다 작으면 왼쪽으로 탐색
        else if (arr[mid] > target) end = mid -1;
        // 찾는 target이 중간값보다 크면 오른쪽으로 탐색
        else start = mid +1;
    }
    return -1;
}

int n, target;
vector<int> arr;

int main()
{
    // 전체 원소의 개수 n, 찾고자 하는 값 target 입력 받기  
    cin >> n >> target;
    
    // 전체 원소 입력받기 
    for(int i=0; i<n; i++)
    {
    	int x;
        cin >> x;
        arr.push_back(x);
    }
    
    //이진 탐색 수행결과 출력
    int result = binarySearch(arr, target, 0, n-1);
    if (result == -1)
    {
    	cout << "원소가 존재하지 않습니다." << '\n';
    }
    else
    {
    	cout << result + 1 << '\n';
    }
    return 0;
}