← 전체 회차
A-028● Day 282026.06.03easyleetcode #704neetcode150

이진 탐색

#array#binary-search
↗ leetcode #704 · binary-search
01

문제

· problem
P.028

이진 탐색

↗ leetcode #704

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어졌을 때, nums에서 target을 찾는 함수를 작성하세요. target이 존재하면 그 인덱스를 반환합니다. 존재하지 않으면 -1을 반환합니다. O(log n) 시간 복잡도의 알고리즘을 작성해야 합니다.

제약
  • · 1 ≤ nums.length ≤ 10⁴
  • · -10⁴ < nums[i], target < 10⁴
  • · All integers in nums are unique
  • · nums is sorted in ascending order
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[-1,0,3,5,9,12]
9
4
example 2input → output
[-1,0,3,5,9,12]
2
-1
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    반환 값이 0-based 인덱스인가요?
  • ☐
    target이 배열에 없으면 정확히 무엇을 반환해야 하나요?
  • ☐
    O(log n) 복잡도 요구사항은 무엇을 의미하나요?
  • ☐
    배열에 중복된 값이 포함될 수 있나요?
  • ☐
    배열을 먼저 정렬해야 하나요?
  • ☐
    모든 요소를 순차적으로 확인하는 선형 탐색이 충분한가요?
  • ☐
    target과 일치하는 모든 인덱스를 반환해야 하나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 포인터 초기화
○
l, r = 0, len(nums) - 1
○
l, r = 0, len(nums)
○
l, r = 1, len(nums) - 1
step 2· 반복 조건
○
while l <= r:
○
while l < r:
○
while l <= r and nums[l] != target:
step 3· 중간값 계산│ 중첩
○
m = l + ((r - l) // 2)  # (l + r) // 2 can lead to overflow
○
m = (l + r) // 2
○
m = (r - l) // 2
step 4· 중간값이 target보다 크면 좌측 탐색│ 중첩
○
if nums[m] > target:
○
if nums[m] >= target:
○
if nums[m] > target: l = m + 1
step 5· 중간값이 target보다 작으면 우측 탐색│ 중첩
○
elif nums[m] < target:
○
elif nums[m] < target: r = m - 1
○
elif nums[m] <= target:
step 6· 결과 반환
○
else:
○
else: return -1
○
if nums[m] == target: return m
else: continue
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def search(self, nums: List[int], target: int) -> int:
3
        l, r = 0, len(nums) - 1
4
5
        while l <= r:
6
            m = l + ((r - l) // 2)  # (l + r) // 2 can lead to overflow
7
            if nums[m] > target:
8
                r = m - 1
9
            elif nums[m] < target:
10
                l = m + 1
11
            else:
12
                return m
13
        return -1
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[-1,0,3,5,9,12]
9
→
4
case 2
[-1,0,3,5,9,12]
2
→
-1
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.