이진 탐색(Binary Search) 알고리즘

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
 
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target:
            return m  # 정답 반환
        elif nums[m] < target:
            l = m + 1  # 중간값보다 크면 오른쪽 구간으로 포인터 이동
        else:
            r = m - 1  # 중간값보다 작으면 왼쪽 구간으로 포인터 이동
 
    return None  # 없으면 None 반환
 
 
nums = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(nums, 7))  # 3
print(binary_search(nums, 8))  # None

def solution(nums, target):
    def lower_bound():
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            # target보다 작으므로,
            # target보다 크거나 같아질때까지 왼쪽 포인터를 오른쪽 구간으로 이동
            if nums[m] < target:
                l = m + 1
            # target보다 크거나 같으므로, 오른쪽 포인터를 중간으로 이동하여 왼쪽 구간 탐색
            else:
                r = m
        return l
 
    def upper_bound():
        l, r = 0, len(nums) - 1
        while l < r:
            m = (l + r) // 2
            # target보다 작거나 같으므로,
            # target보다 큰 값을 만날때까지 왼쪽 포인터를 오른쪽 구간으로 이동
            if nums[m] <= target:
                l = m + 1
            # target보다 크므로, 오른쪽 포인터를 중간으로 이동하여 왼쪽 구간 탐색
            else:
                r = m
        return l
 
    left = lower_bound()
    if left == 0 and nums[0] != target:  # target이 배열에 없는 경우는 0 바로 반환
        return 0
 
    right = upper_bound()
    return right - left
 
 
nums = [1, 2, 2, 2, 3, 4, 5]
print(solution(nums, 2))  # 출력: 3
print(solution(nums, 6))  # 출력: 0