어떤 조건을 만족하는 위치 중 가장 큰 or 작은 위치는?

💡 이분 탐색

정렬된 배열에서 target의 존재 여부와 위치를 알려준다.
재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다.

💡 매개 변수 탐색

이분 탐색과 유사하다.
탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다.
최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다.

• 최적화 문제 : 어떤 알고리즘의 최적 솔루션을 찾는 것
• 결정 문제 : 답이 이미 결정되어 있다고 보고 문제를 푸는 것

이진 탐색과 매개 변수 탐색의 차이점

: 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개 변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다.

따라서, 매개 변수 탐색은 어떤 조건을 만족하는 위치 중 가장 크거나 작은 값을 찾을 때 사용한다.

1. 어떤 시점까지 조건을 만족하지만 그 후로 만족하지 않는 경우, 조건을 만족하는 최댓값 찾기
2. 어떤 시점까지 조건을 만족하지 않지만 그 후로는 조건을 만족하는 경우, 조건을 만족하는 최소값 찾기

📍 매개 변수 탐색 구현 (bj1654)

int answer = 0; 	// 정답 (조건 만족하는 max값)

while(low <= high) {	// break문 없이 모든 배열을 탐색한다 
    int mid = (low + high) / 2;

    if (isPossible(mid)) {  // 조건을 만족한다면 길이 늘리기
        if (mid > answer)	// 정답 업데이트 
            answer = mid;
        low = mid + 1; 
    }
    else {  // 조건 만족하지 않으면 길이 줄이기 
        high = mid - 1;
    }
}

관련 문제 - 백준 1654번: 랜선 자르기 , 백준 2805번: 나무 자르기, 백준 2110번: 공유기 설치

참고 링크 - https://annajeong.github.io/algorithm/parametric/