[자료구조] 이진탐색 (Binary Search) 파이썬 (bisect, recursion, iteration)

일반적인 풀이방법

def solution(L, x):
    start, end = 0, len(L)-1
    
    while start <= end:
        mid = (start + end)//2
        if L[mid] == x:
            return mid
        elif L[mid] < x:
            start = mid + 1
        else:
            end = mid-1
    else:
        return -1

파이썬 bisect 함수 사용

import bisect
def solution(L, x):
    i = bisect.bisect_left(L, x)
    if i < len(L) and L[i] == x:
        return i
    else:
        return -1

bisect_left(a, x)의 결과가 i 라 할 때, a[i]는 x보다 크거나 작은 값일 수 있다. 따라서 a[i]가 x와 같은지를 체크해야 한다.  또한 bisect_left() 함수는 x가 a에 존재하는지 여부는 관심이 없기 때문에 a의 모든 원소보다 x가 크다면 i는 len(a)와 같은 값이 나올 것이다. 이 경우는 x가 존재하지 않는 것으로 본다.

 

파이썬 recursion

def binary_search(arr, low, high, x):
 
    # Check base case
    if high >= low:
 
        mid = (high + low) // 2
 
        # If element is present at the middle itself
        if arr[mid] == x:
            return mid
 
        # If element is smaller than mid, then it can only
        # be present in left subarray
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
 
        # Else the element can only be present in right subarray
        else:
            return binary_search(arr, mid + 1, high, x)
 
    else:
        # Element is not present in the array
        return -1

def solution(L, x):
    return binary_search(L, 0, len(L)-1, x)
    

 

 

 

 

bisect 풀이 출처: https://soooprmx.com/archives/8722

bisect reference: docs.python.org/ko/3/library/bisect.html

재귀함수 출처: www.geeksforgeeks.org/python-program-for-binary-search/