이분탐색 알고리즘

정렬된 배열에서 어떠한 값을 빠르게 찾을 때 사용할 수 있는 알고리즘이다.
배열의 양 끝을 가리키는 인덱스를 left = 0, right = N - 1로 설정하고 mid = (left + right) / 2로 설정한 후,
인덱스 mid에 해당하는 값과 찾는 값을 비교하여 mid에 있는 값보다 작으면 right = mid - 1로 세팅한다.
만약, mid에 있는 값보다 크면 left = mid + 1로 세팅한다.
이렇게 진행하면 한번 반복할 때마다 탐색해야하는 탐색 범위가 반씩 줄어드는 것을 알 수 있다 .

이분탐색의 사용 유형

이분탐색을 활용하여 파라매트릭 서치(Parametric Search) 유형을 해결할 수 있다.
파라매트릭 서치(Parametric Search)이란 특정 범위 내에서 조건을 만족하는 어떠한 값을 찾는 방법론이다.
파라매트릭 서치는 가능한 해의 영역이 연속적이어야 한다. 예를 들어, 어떤 조건을 만족하는 최솟값을 구한다면 x 이상의 값들도 조건을 만족해야 하고, 어떤 조건을 만족하는 최댓값을 구한다면 x 이하의 값들도 조건을 만족해야 한다.

예제 1

• 범위 : 1 ~ 802 (가능한 랜선의 길이)
• 조건 : 주어진 모든 랜선을 잘라 그 갯수가 11이 돼야 함.
• 해석 : 범위 내에서 조건을 만족시키는 값을 찾는 문제이면서, 만약 답이 200이면 199로 잘라도 11개가 나오고 198로 잘라도 11개가 나오므로 가능한 해의 영역이 연속적이다 --> 파라매트릭 서치
• 풀이 : min을 1, max를 주어진 길이 중 최대 숫자로 설정하고 mid는 (max + min) / 2로 설정한다.
  만약 mid로 모든 랜선을 잘랐을 때, 랜선의 갯수가 주어진 목표 갯수보다 작으면 길이가 더 작아야 하므로 max를 mid - 1로 세팅하고, mid로 모든 랜선을 잘랐을 때, 랜선의 갯수가 주어진 목표 갯수보다 같거나 크면 길이가 더 길어져야 하므로 min을 mid + 1로 세팅한다. 이렇게 max와 min이 같아질 때까지 탐색한다.

예제 2

• 범위 : 1 ~ 9 (좌표의 가장 끝과 끝)
• 조건 : 말을 최대한 떨어뜨려서 5개의 좌표 중 세 곳에 놓아야 함.
• 해석 : 범위 내에서 말 사이의 거리를 구하고, 말을 배치할 수 있는지 판단하는 문제로, 만약 가장 가까운 두 말의 최대 거리가 3 보다 작을 때에도 말을 배치할 수 있으므로 가능한 해의 영역이 연속적이다. --> 파라매트릭 서치