[알고리즘] Binary Search - Python

이진 탐색 - 바이너리 서치(Binary Search)

• BigO - O(logN)
• 탐색할 자료를 반씩 나누어가며 탐색하는 방법
• 자료는 정렬된 자료여야 함

 

 

구현을 위한 준비

• target - 찾아야 하는 값
• list - 값들이 담겨 있는 리스트
• start - list의 첫 인덱스 위치
• end - list의 마지막 인덱스 위치
• mid - start와 end의 중간 인덱스 위치

 

 

 

바이너리 서치는 값을 O(logN) 시간안에 찾을 수 있는 효율적인 알고리즘이다.

리스트의 시작과 끝을 가지고 중간을 만들어 타겟과 비교하여 전체 리스트의

탐색 범위를 1/2씩 줄인다.

 

binary_search 구현 (반복적 알고리즘)

def binarySearch(target, list):
    list.sort() # list 정렬
    start, end = 0, len(list)-1 # 시작과 끝 인덱스

    while(start <= end): # start가 end보다 커질 때까지    
        mid = (start + end) // 2 # 중간 인덱스 위치
        
        if(target == list[mid]): # 타겟과 리스트의 중간 인덱스 값이 같다면
            return mid # 값 리턴

        elif target > list[mid]: # 타겟이 중간 인덱스 값보다 크다면
            start = mid+1 # 시작 인덱스를 중간 인덱스 + 1로 바꿈
        else: # 타겟이 중간 인덱스 값보다 작다면(target < list[mid])
            end = mid-1 # 끝 인덱스를 중간 인덱스 - 1로 바꿈

    return None # 값을 찾지 못한 경우


if __name__ == "__main__":
    list = [3,5,7,1,2,9,12]
    target = 2
    idx = binarySearch(target, list)

    if idx:
        print("{}을 찾았습니다.".format(list[idx]))
    else :
        print("찾으시는 {}가 존재하지 않습니다.".format(target))

 

binary_search 구현 (재귀적 알고리즘)

def binarySearchRecursion(target, list, start, end):
    if(start > end): # 타겟이 없다면
        return None
    mid = (start + end) // 2

    if(target < list[mid]): # 타겟이 리스트의 중간 인덱스 값보다 작다면
        return binarySearchRecursion(target, list, start, mid-1)
    elif(target > list[mid]): # 타겟이 리스트의 중간 인덱스 값보다 크다면
        return binarySearchRecursion(target, list, mid+1, end)
    else: # 타겟이 리스트의 중간 인덱스 값과 같다면
        return mid
    


if __name__ == "__main__":
    list = [3,5,7,1,2,9,12]
    target = 2
    list.sort()
    idx = binarySearchRecursion(target, list, 0, len(list)-1)

    if idx:
        print("{}을 찾았습니다.".format(list[idx]))
    else :
        print("찾으시는 {}가 존재하지 않습니다.".format(target))