이진 탐색

Binary search

• 배열이 정렬되어 있을 경우, 절반씩 줄여나가면서 탐색하는 기법
• 이진 탐색을 사용하기 위해서 배열이 꼭 정렬되어 있어야 한다!!
• left = 0, right = 배열의 길이 - 1, mid = (left + right) // 2로 시작해서 만약 찾고자 하는 값이 mid 인덱스에 해당하는 값보다 크면 left = mid + 1로 바꿔주고 찾고자하는 값이 mid 인덱스에 해당하는 값보다 작으면 right = mid - 1로 바꿔주면서 left가 right보다 크거나 같을 때까지 반복해준다!

예시 - 4의 위치 찾기

• a = [1, 2, 3, 4, 5, 6, 7, 8] 일 때, left = 0, right = 1, mid = (left + right) // 2 = 3 로 시작한다
• a[mid]가 4보다 크므로 right = mid - 1 = 2로 바꿔준다!
• mid = (left+right)//2 = 1로 바꿔준다!

• a[mid]가 4보다 크므로 left = mid + 1 = 2로 바꿔준다!
• mid = (left + right) // 2 = 2로 바꿔준다!

• a[mid]가 4이므로 mid를 리턴!

소스코드

• 반복문

def binary_search_loop(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1
    # 못찾으면 -1 반환
    return - 1

a = [1, 3, 5, 7,10]
print(binary_search_loop(a, 7))

• 재귀

def binary_search_recursive(nums, target):
    def binary_search(left, right):
        if left > right:
            return -1

        mid = (left + right) // 2

        if nums[mid] < target:
            return binary_search(mid + 1, right)
        elif nums[mid] > target:
            return binary_search(left, mid - 1)
        else:
            return mid

    return binary_search(0, len(nums) - 1)