[Programming/Algorithm] 이진 탐색 알고리즘

이진 탐색 알고리즘을 요약하면 다음과 같다

• 리스트의 모든 데이터는 정렬된 상태여야 한다.
• 첫 번째 인덱스를 start로 설정하고 마지막 인덱스를 end로 설정한다.
• 가운데 인덱스를 mid로 설정하고 mid 데이터와 target 데이터를 비교한다.
• target 데이터와 mid 데이터가 같다면 mid를 반환한다.
• target 데이터가 작다면 end를 mid-1로 한다.
• target 데이터가 크면 start를 mid+1로 한다.
• 데이터를 찾거나 start와 end가 교차하기 전까지 계속 진행한다.
• 데이터를 찾지 못했다면 -1 혹은 None을 반환한다.

이진 탐색 알고리즘을 적용하려면 반드시 데이터가 정렬된 상태여야 한다. 이미 정렬이 상태이므로 target이 mid의 데이터보다 작다는 것은 mid 이후 데이터는 모두 target보다 크다는 의미이다. 즉, mid보다 인덱스가 작은 데이터만 비교하면 된다.

반대로 target이 mid 데이터보다 크다는 것은 mid 이전 데이터는 모두 target보다 작다는 것을 의미한다. 즉, mid보다 인덱스가 큰 데이터만 비교하면 된다.

python

# 반복문을 이용한 이진 탐색 알고리즘
def binary_search(li: list, target: int) -> int:
    length = len(li)
    start = 0
    end = length - 1
    while start <= end:
        mid = (start + end) // 2
        if target > li[mid]:
            start = mid + 1
        elif target < li[mid]:
            end = mid - 1
        else:
            return mid
    return -1


# 재귀 함수 호출을 이용한 이진 탐색 알고리즘
def recursion_bsearch(li: list, target: int) -> int:
    def inner(_start: int, _end: int) -> int:
        if _start > _end:
            return -1
        _mid = (_start + _end) // 2
        if target > li[_mid]:
            return inner(_mid + 1, _end)
        elif target < li[_mid]:
            return inner(_start, _mid - 1)
        else:
            return _mid
    return inner(0, len(li) - 1)


if __name__ == '__main__':
    ll = [i * 10 for i in range(10)]
    ll.sort()
    print(ll)

    print('while find: {}'.format(binary_search(ll, 70)), end='\n')
    print('recursion find: {}'.format(recursion_bsearch(ll, 70)), end='\n')


""" 결과

[0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
while find: 7
recursion find: 7

"""

C++

#include <iostream>

using std::cout;
using std::cin;
using std::endl;


int BinarySearch(const int ar[], const int len, const int target){
    int start, end, mid;
    start = 0;
    end = len - 1;
    while(start <= end){
        mid = (start + end) / 2;
        if(target < ar[mid]){
            end = mid - 1;
        }
        else if(target > ar[mid]){
            start = mid + 1;
        }
        else{
            return mid;
        }
    }
    return -1;
}

int FindValue(const int ar[], const int start, const int end, const int target){
    int mid = (start + end) / 2;
    if(target == ar[mid]){
        return mid;
    }
    else if(target < ar[mid]){
        return FindValue(ar, start, mid - 1, target);
    }
    else{
        return FindValue(ar, mid + 1, end, target);
    }
    return -1;
}

int BinarySearchRecur(const int ar[], const int len, const int target){
    return FindValue(ar, 0, len - 1, target);
}


int main(int argc, const char * argv[]) {
    int arr[] = {2, 5, 10, 15, 30, 45, 55};
    int arrlen = sizeof(arr) / sizeof(int);
    
    cout<<"while find: "<<BinarySearch(arr, arrlen, 30)<<endl;
    cout<<"recursion find: "<<BinarySearchRecur(arr, arrlen, 30)<<endl;
    cout<<endl;

    return 0;
}


/* 결과

while find: 4
recursion find: 4

*/

---

이진 탐색 알고리즘의 성능

mid데이터와 target데이터를 한 번 비교할 때마다 비교해야 할 데이터 개수는 절반으로 줄어든다. 따라서 알고리즘의 성능은 O(log n) 이다.