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

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

정렬되어있는 리스트가 있을 때, 가운데 값과 비교해나가면서 가능한 정답의 범위를 절반으로 줄여나가며 어떤 수가 존재하는 지, 존재하지 않는 지 찾는 알고리즘

언제 이용?

• 정답을 구하는 문제

  A에서 B까지 가는 가장 빠른 시간을 구하는 것 - 최적화

  가능여부를 판별하는 문제로 바꾸기 가능

• 가능한지 살펴보는 문제

  A에서 B까지 X라는 시간으로 이동할 수 있을까? - YES/NO

ex. A에서 B까지 가는 가장 빠른 시간이 M인 경우

M보다 빠른 시간 - 모두 불가능

M보다 큰 시간 - 모두 가능

문제에 주어지는 기준 점(X)를 통해 가능성 여부를 따져서 정답을 찾아낸다.


이분 탐색에 해당하는 문제
랜선 자르기 : https://www.acmicpc.net/problem/1654나무 자르기 : https://www.acmicpc.net/problem/2805공유기 설치 : https://www.acmicpc.net/problem/2110