자네

그거 아는가?

이진 탐색엔 여러가지 기법이 있다네

첫번째로는 일반적인 방법인,
정확히 일치하는 값 찾기가 있고
두번째로는…

…


…..



……..




농담이고

다른 방법으론

왼쪽 경계(lower_bound)

오른쪽 경계(upper_bound)

조건 탐색(Parametric Search)이 있다

이 이상도 있다만 그건 나중에 다루겠다.
시간되면 ㅇㅇ
(안한다는 뜻)

왼쪽 경계 (lower_bound)

개념

정렬된 배열에서 target 이상이 처음 등장하는 인덱스를 찾는 이분 탐색 기법.
삽입 위치, 중복 원소의 시작 인덱스, 구간 내 존재 판별 등에 많이 씀.

예시

arr = [1, 3, 3, 5, 7, 9]
target = 3
# lower_bound(arr, 3) → 1 (첫 번째 3의 위치)
target = 4
# lower_bound(arr, 4) → 3 (5의 위치: 4 이상인 첫 원소)

오른쪽 경계 (upper_bound)

개념

정렬된 배열에서 target을 초과하는 값이 처음 나오는 인덱스를 찾는 이분 탐색 기법.
특정 값의 끝 위치, 값의 개수 구하기 등에 자주 씀.

예시

arr = [1, 3, 3, 5, 7, 9]
target = 3
# upper_bound(arr, 3) → 3 (5의 위치: 3 초과하는 첫 원소)
target = 7
# upper_bound(arr, 7) → 5 (9의 위치: 7 초과하는 첫 원소)

조건 탐색 (Parametric Search)

개념

특정 조건(가능/불가능)을 만족하는 값 중 최적값(최소/최대/임계값)을 찾기 위해
이분 탐색을 응용하는 기법.
정렬된 배열만이 아니라 다양한 조건문에 적용 가능.

예시

• 자를 높이 h를 이분 탐색.

• 각 h마다 “이 높이로 잘랐을 때 원하는 양을 얻을 수 있는가?”를 판별.

• 만족하면 더 높은 h, 불만족이면 더 낮은 h로 탐색 범위를 조절해 최적값을 찾음.

간단히 말해 상황보고 만들면
파라메트릭 서치다

비교