[알고리즘] 7. 이분 탐색 (Binary Search)

이분탐색은 앞서 분할 정복 파트에서 쓰였죠?
근데 이 이분 탐색 자체가 문제풀이의 키가 되는 경우도 많아요.
바로 parametric search의 방법으로 이분 탐색을 이용하는 거다~~
이게 뭐냐면? 문제의 답을 구하지 않고 그냥 아무거나 툭툭 던져보며 답을 찾아가는 거. (물론 ㄹㅇ 아무거나가 아니구 최대한 유용한 정보를 얻도록 던지는 거지)

🖊 예시로 이해하기

나무 자르기

나무의 최대높이를 end, start는 0으로 두고,
start와 end를 갱신해나간다. 그럼 mid = (start+end)/2 !
갱신하는 기준은?

만약 자른 나무토막의 합이 M (= 필요한 나무의 길이)보다 작다면?
나무를 더 잘라야 한다는 거니까 절단기의 높이를 낮춰야 한다 -> end = mid
반대상황에는 나무를 덜 잘라도 된다는 거니까 절단기의 높이를 높인다! -> start = mid

이렇게 해나가다가 start와 end 구간이 1이게 되면 start가 바로 답이다!!

출처 - 라이님 블로그

💙 스터디 예제

◼ ch13

🔘III 2805 나무자르기
🔘III 2512 예산
🔘III 2121 넷이 놀기
🔘III 19637 IF문 좀 대신 써줘
🔘I   2343 기타 레슨
🔘III 1654 랜선 자르기
🟡III 21774 가희와 로그 파일
🔘I   2110 공유기 설치
🟡II  1561 놀이공원
🟡III 1300 K번째 수