Binary Search

# Binary Search

이진탐색은 오름차순 정렬되어 있는 리스트 내에서 특정 값의 인덱스를 찾는 알고리즘 입니다.

 

[ 아래 그림과 같은 숫자 리스트에서 7의 위치를 찾는 가장 효율적인 방법은 무엇일까요? ] 

리스트 처음부터 순환하면서 7의 인덱스까지 찾아가는 방법도 있겠지만, 이 방법은 시간복잡도 O(N)이 소요되므로 데이터의 크기가 클수록 비효율적이게 됩니다.

이때, 우선 리스트의 중간 값인 11을 찾습니다. 이 리스트는 정렬되어 있기 때문에 11을 기준으로 왼쪽은 11보다 작은 수, 오른쪽은 11보다 큰 수가 있게 됩니다. 우리가 찾아야하는 숫자 7은 11보다 작기 때문에 왼쪽에 위치하게 됩니다. 이렇게 리스트를 반 나누고 탐색하고 반 나누고 탐색하고를 반복하여 7의 위치를 찾게됩니다.

binary는 숫자 두개를 의미하는데, 한번 수행할 때마다 절반씩 나누어서 사이즈를 줄여 나가면서 탐색하기 때문에 binary search라고 합니다. 한번 수행할 때마다 절반씩 훅훅 줄여나가기 때문에 밑이 2인 시간복잡도 O(logN)을 가집니다. 예를 들어 N=100이라고 하면 log100은 약 6.64이므로, 데이터 100개가 존재할 때 무조건 7번 이내에 데이터를 찾을 수 있습니다.

그래서 우리는 indexof오 같이 인덱스로 데이터 위치를 찾을 때 이진탐색이 무조건 편리하겠다고 생각할 수 있지만, 이진탐색은 정렬된 리스트에서만 사용가능하다는 제약이 존재합니다.

 

 

# 코드 구현(Python)

binary search은 중간 인덱스 값을 찾고, 중간 인덱스를 기준으로 array를 절반으로 나누고, target data의 위치가 절반의 왼쪽인지 오른쪽인지를 판단하면서 target값을 찾아나가는 과정입니다.

실제로 array를 직접 절반으로 나누고, 새로 array를 선언하고 할당하는 과정을 거치면 추가적인 메모리공간을 사용하게 되며,  array를 할당하는 과정에서 시간복잡도도 늘어나게 됩니다. 그래서 인덱스를 통해서 절반씩 줄여나가며 코드를 구현하겠습니다.

def BinarySearch(arr, target):
    l = 0
    r = len(arr)-1  
    while l<=r:
        m = l + ((r-l)//2)
        if arr[m] < target:
            l = m+1
        elif arr[m] > target:
            r = m-1
        else:
            return m
    return -1

arr : 정렬된 데이터 집합
target :  찾고자하는 데이터 값

l = 0                   왼쪽 맨 끝 인덱스
r = len(arr)-1      오른쪽 맨 끝 인덱스
while l<=r:        이진탐색이 종료되는 포인트는 2가지로 볼 수 있습니다. 첫째는 우리가 원하는 target data를 찾았을 때 입니다. 둘째는, l이 r보다 작을 때 까지 수행하는 것입니다. l이 r보다 크다는 것은 사실상 모든 데이터를 다 탐색했다는 것이기 때문입니다.

    m = l + ((r-l)//2)         m = (l + r) / 2를 해버리면, overflow exception이 발생할 수 있으므로 m = 1 + ((r-l)/2)로 계산합니다.

    if arr[m] < target:
        l = m+1                        **위 그림 참고
    elif arr[m] > target:
        r = m-1                        **위 그림 참고
    else:                               arr[m] == target 이면 m의 위치 반환
        return m
return -1

 

[ Test Code ] 

if __name__ == '__main__':
    arr = [1,2,3,4,5,6,7,8,9]
    print(BinarySearch(arr,3)) #2
    print(BinarySearch(arr,7)) #6

 

 

# 전체 코드

깃허브에서 테스트 코드를 포함한 전체 코드를 보실 수 있습니다.

GitHub - sonzwon/TIL: Today I Learned