[Algorithm] 이분탐색(Binary search algorithm, 이진 검색 알고리즘)

이분탐색이란?

 

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이다. 재귀와 반복문으로 구현할 수 있다.

 

7이 target인 경우

 

재귀 함수로 구현한 이분 탐색

def binary_search(array,target,start,end):
    if start > end:
        return None

    mid = (start + end)//2
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array,target,start,mid-1)
    else:
        return binary_search(array,target,mid+1,end)

a = [1,2,3,4,5]
target = 2
print(f"이분 탐색 결과 : {binary_search(a,target,0,len(a)-1)}")

 

반복문으로 구현한 이분 탐색

def binary_search2(array,target,start,end):
    while start <= end:
        mid = (start+end)//2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

a = [1,2,3,4,5]
target = 2
print(f"이분 탐색 결과 : {binary_search2(a,target,0,len(a)-1)}")