이진 탐색

성립 조건 (매우 중요)

• 탐색 대상 구간이 정렬되어 있어야 합니다.
• 정렬 기준과 탐색 비교 기준이 같아야 합니다(오름차순 정렬 후 오름차순 비교).
• 인덱스로 직접 구현하는 이진 탐색은 array/vector처럼 랜덤 접근 가능한 구조에서 가장 효율적입니다.

---

핵심 아이디어

• 가운데(mid)를 보고, 정답이 있을 수 있는 절반만 남깁니다.
• 매 단계마다 탐색 범위가 절반이 되므로 비교 횟수가 급격히 줄어듭니다.

이진 탐색 과정 시각화 (81 찾기)

numbers = {1, 8, 15, 23, 32, 44, 56, 63, 81, 91}
인덱스:    0  1   2   3   4   5   6   7   8   9

1단계: left=0, right=9, mid=4 (32)
       81 > 32 -> 오른쪽 절반만 남김 -> left=5

2단계: left=5, right=9, mid=7 (63)
       81 > 63 -> 오른쪽 절반만 남김 -> left=8

3단계: left=8, right=9, mid=8 (81)
       81 == 81 -> 찾음

---

직접 구현 (안전한 반복문 버전)

int BinarySearchIndex(const vector<int>& numbers, int target) {
    int left = 0;
    int right = static_cast<int>(numbers.size()) - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // overflow 방지

        if (numbers[mid] == target) {
            return mid;
        }
        if (numbers[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // 못 찾음
}

핵심 포인트:

• mid = left + (right - left) / 2를 권장합니다(left + right overflow 방지).
• 빈 벡터에서도 right = -1로 시작해 루프를 안전하게 건너뜁니다.
• 범위 갱신 시 left = mid + 1 또는 right = mid - 1처럼 반드시 mid를 제외해야 무한 루프를 막을 수 있습니다.

---

시간 복잡도

• 비교 횟수 기준으로 O(log N).
• 예: N = 1024면 대략 10번 비교(log2(1024) = 10).

O(log N) 직관

N=1024 -> 512 -> 256 -> 128 -> ... -> 1   (약 10단계)
N=8    -> 4   -> 2   -> 1                 (3단계)

---

STL 버전: binary_search, lower_bound, upper_bound

vector<int> v{1, 3, 3, 3, 7, 9}; // 정렬되어 있어야 함

bool exists = binary_search(v.begin(), v.end(), 3); // 존재 여부(bool)

auto lb = lower_bound(v.begin(), v.end(), 3); // 첫 번째 >= 3
auto ub = upper_bound(v.begin(), v.end(), 3); // 첫 번째 > 3

if (lb != v.end() && *lb == 3) {
    size_t firstIdx = static_cast<size_t>(lb - v.begin());
    size_t count = static_cast<size_t>(ub - lb); // 값 3의 개수
}

• binary_search는 존재 여부만 알려줍니다.
• "위치"나 "중복 구간"이 필요하면 lower_bound/upper_bound가 더 유용합니다.
• 위 함수들은 <algorithm> 헤더가 필요합니다.

---

list와의 관계 (정확히 이해)

• 인덱스 기반 수동 구현은 list에 맞지 않습니다(operator[] 없음).
• std::binary_search(list.begin(), list.end(), x)는 문법상 가능하지만,
  이터레이터 이동 비용 때문에 실무에서 체감 성능 이점이 거의 없습니다.
• 탐색 성능이 중요하면 보통 vector + 정렬 + lower_bound 조합을 사용합니다.

---

자주 하는 실수 + 체크 질문

자주 하는 실수

실수	문제
정렬하지 않은 데이터에 이진 탐색 적용	결과가 틀려도 눈치채기 어려움
mid = (left + right) / 2만 고집	큰 인덱스에서 overflow 위험
left = mid, right = mid로 갱신	무한 루프 가능
binary_search로 위치까지 얻으려 함	bool만 반환

체크 질문 (스스로 답해보기)

• binary_search와 lower_bound의 목적 차이를 설명할 수 있는가?
• 중복 값이 있을 때 "첫 위치"와 "개수"를 어떻게 구하는가?
• 왜 left + (right - left) / 2가 더 안전한가?

---