03 - 이진탐색

이진탐색(Binary Search)은 정렬된 배열(오름차순/내림차순)에서

원하는 값을 찾을 때, 탐색 범위를 절반씩 줄여가며 찾는 방법입니다.

 

핵심 조건

• 데이터가 정렬돼 있어야 함 (이게 1순위 조건)
• 배열처럼 인덱스로 중간 접근이 빠른 자료구조에 적합(리스트/배열)

동작 원리

1. low(시작), high(끝) 잡기
2. mid = (low + high) // 2
3. arr[mid]와 target 비교
   • 같으면 찾음
   • arr[mid] < target이면 오른쪽 반쪽 탐색 (low = mid + 1)
   • arr[mid] > target이면 왼쪽 반쪽 탐색 (high = mid - 1)
4. low > high가 되면 없음

시간복잡도

• 탐색: O(log n)
• 공간: 반복문 구현이면 O(1) (재귀는 콜스택 때문에 O(log n))

 

이진탐색을 이용한 문제풀이

 

Q. 1에서 16까지 오름차순으로 정렬되어 있는 배열이 있다.

이 배열 내에 14가 존재한다면 True, 존재하지 않는다면 False 를 반환하시오

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_sequential(target, array):
    find_count = 0
    for number in array:
        find_count += 1
        if target == number:
            print(find_count)
            return True

    return False


result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True