Binary Search

이진탐색

 

정렬된 배열을 절반씩 줄여나가면서 탐색하는 기법

 

https://leetcode.com/problems/binary-search/

Binary Search - LeetCode

 

구현

 

def bs1(lst, target):
    def bs(start_index, end_index):
        # start_index 와 end_index가 == 경우 해당 값을 찾은 경우 이므로 -1을 리턴하면 안된다.
        if start_index > end_index:
            return -1

        mid = (start_index + end_index) // 2

        if lst[mid] < target:
            return bs(mid+1, end_index)
        elif lst[mid] > target:
            return bs(start_index, mid-1)
        else:
            return mid

    return bs(0, len(lst) - 1)

assert bs1(lst=[1,2,3,4,5], target=3) == 2

 

내장함수

 

def bisect_left(*args, **kwargs): # real signature unknown
    """
    Return the index where to insert item x in list a, assuming a is sorted.
    
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.
    
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    pass

def bisect_right(*args, **kwargs): # real signature unknown
    """
    Return the index where to insert item x in list a, assuming a is sorted.
    
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
    insert just after the rightmost x already there.
    
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """
    pass

각각의 내장 함수가 어떤 값을 반환하는지 하나씩 살펴보자

 

import bisect
lst = [-1,1,2,2,2,3,4]
bisect.bisect_left(lst, 2)
==> 2 # target 값의 가장 앞쪽 인덱스를 return 한다.

lst = [-1,1,3,4,5]
bisect.bisect_left(lst, 2)
==> 2 # target 값보다 같거나 큰 범위에서의 가장 앞쪽 인덱스를 return 한다.

lst = [-5, -4, -3, -2,-1]
bisect.bisect_left(lst, 0)
==> 5 # return 값이 해당 리스트의 길이를 넘어선 값이다.
# 즉, 주어진 list 보다 큰 수를  target하면 리스트의 길이보다 큰 값을 return 한다.

lst = [3,4,5,6,7]
bisect.bisect_left(lst, 2)
==> 0
# lst 에 value보다 작은 값을 target으로 설정 시 0을 return 한다.

lst = [1,2,2,2,4,5]
bisect.bisect_right(lst, 2)
==> 4 # right 내장 함수를 사용 시 return 값은 target 값 보다 큰 값의 인덱스를 return 한다.