[정글 베이직 11] — 이분 탐색 (Binary Search)

 

week 03 start

#이분탐색#BinarySearch#탐색#크래프톤정글#베이직#3주차#Python

📋 문제 소개

문제 설명

정렬된 배열에서 특정 값(target)을 찾아 해당 인덱스를 반환한다. 배열을 반으로 나누어 탐색 범위를 절반씩 줄이는 이분 탐색 알고리즘을 직접 구현한다.

INPUT

정렬된 정수 배열 arr, 찾을 값 target

OUTPUT

target의 인덱스 (없으면 -1)

예제

입력

arr = [1, 3, 5, 7, 9, 11, 13] target = 7

출력

3

💡 힌트

left, right 포인터와 mid = (left+right)//2 사용. arr[mid]와 target 비교해 범위 조정.

① 문제 이해

항목	내용
문제	정렬된 배열에서 target 값의 인덱스를 반환. 없으면 -1.
입력	정렬된 정수 배열 arr, 찾을 값 target
예제	[1,3,5,7,9,11,13], target=7 → 인덱스 3

② 핵심 아이디어

배열을 반으로 나눠 탐색 범위를 절반씩 줄인다. mid를 계산하고 target과 비교해 left 또는 right 포인터를 이동한다.

# 수도코드
left = 0, right = len(arr)-1
while left <= right:
    mid = (left+right) // 2
    arr[mid] == target  →  return mid
    arr[mid] >  target  →  right = mid-1
    arr[mid] <  target  →  left  = mid+1
return -1

③ 코드 분석

def binary_search(arr, target):
    left  = 0
    right = len(arr) - 1           # ① 마지막 인덱스

    while left <= right:            # ② <= 필수
        mid = (left + right) // 2  # ③ 중간 인덱스

        if arr[mid] > target:
            right = mid - 1        # ④ 왼쪽으로 축소
        elif arr[mid] < target:
            left  = mid + 1        # ⑤ 오른쪽으로 축소
        else:
            return mid             # ⑥ 찾음

    return -1                      # ⑦ 없으면 -1

번호	코드	의미
①	right = len(arr)-1	인덱스는 0-based이므로 마지막은 len-1
②	left <= right	< 로 쓰면 left==right 순간 마지막 원소 미검사
③	(left+right)//2	정수 나눗셈으로 mid 계산
④⑤	mid±1	mid는 이미 확인했으므로 ±1로 배제
⑦	return -1	루프 종료 = 배열에 없음

④ 자주 하는 실수

⚠️ while left < right 로 쓰는 경우

left==right 순간 루프가 멈춰 마지막 원소를 검사하지 못한다. 반드시 <= 를 써야 한다.

⚠️ right = len(arr) 초기화

인덱스는 0-based. len(arr)-1 이어야 한다.

💡 코드 내 pass 구문은 실행에 영향 없다. TODO 정리 후엔 삭제하는 습관을 들이자.

⑤ 시간복잡도

항목	값	이유
시간	O(log n)	매 단계 탐색 범위가 절반으로 줄어든다
공간	O(1)	포인터 3개만 사용

⑥ 핵심 정리

• 정렬된 배열에서만 사용 가능하다.
• 조건 left <= right — < 아님.
• 포인터 이동은 항상 mid±1 — mid는 이미 확인했다.
• 못 찾으면 return -1.