이진 탐색 기본

순차 탐색 : 리스트 안 특정한 데이터를 찾기 위해 앞에서부터 하나씩 확인하는 방법

이진 탐색 : 정렬 되어있는 리스트에서 탐색 범위를 절반씩 좁혀 데이터를 탐색하는 방법

  - 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.

 

class BinarySearch:
    def __init__(self, array) -> None:
        self.m_array = array

    # 재귀적으로 구현
    def SearchRecur(self, target : int) ->int:
        return self._searchRecur(target, 0, len(self.m_array) - 1)

    def _searchRecur(self, target : int, left : int, right : int) -> int:
        if left > right :
            return None
        
        middle = (right + left ) // 2
        if self.m_array[middle] == target :
            return middle
        elif self.m_array[middle] > target:
            return self._searchRecur(target, left, middle - 1)
        else :
            return self._searchRecur(target, middle + 1, right)       


    # while로 구현
    def SearchWhile(self, target : int) ->int:
        left = 0
        right = len(self.m_array) - 1
        while (left < right):
            mid = (left + right) // 2
            if self.m_array[mid] == target:
                return mid
            elif self.m_array[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        return None

n, target  = list(map(int, input().split()))
g_array = list(map(int, input().split()))

bs = BinarySearch(g_array)
print(bs.SearchRecur(target))
print(bs.SearchWhile(target))
****************
3
None

알아두면 유용한 함수

bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

 

 

출처 : (이코테 2021 강의 몰아보기) 5. 이진 탐색 - YouTube