진행

• L > R 될 때까지 반복
• mid = (L+R)//2
• update
  • mid == k
    : return mid
  • mid > K
    : R = mid-1
  • mid < k
    : L = mid+1

참고하면 좋은 정리 글

https://www.acmicpc.net/blog/view/109

정리

🧭 Binary Search (이진 탐색)의 목적

• 정렬된 배열(리스트) 에서 특정 값(target) 을 빠르게 찾는 것
  — 단순 탐색은 O(n),
  — 이진 탐색은 O(log n) (훨씬 빠름)

⚙️ 동작 원리

• 1배열이 정렬돼 있어야 함
  예: [1, 3, 5, 7, 9, 11]

• 중간값(mid)과 target을 비교

• target < arr[mid] → 왼쪽 구간 탐색
  target > arr[mid] → 오른쪽 구간 탐색

• 일치하면 인덱스를 리턴,
  없으면 탐색 구간이 비워지고 종료.

리턴하는 값

• 찾으면 → 그 값의 인덱스 (위치)
• 못 찾으면 → 보통 -1 또는 삽입될 위치(index)
  (구현 목적에 따라 다름)

코드

def binary_search(target, arr):
    arr.sort()
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if data[mid] == target:
            return mid # 함수를 끝내버린다.
        elif data[mid] > target:
            right = mid -1
        else:
            left = mid + 1
  
    return -1

reference

https://wayhome25.github.io/cs/2017/04/15/cs-16/