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

이분탐색 

N개의 수가 크기 순서대로 배열되어 있을 때 

특정 수 K가 몇 번째 위치에 있는지 빠르게 찾는 방법

 

한 가운데에 있는 수를 보자

짝수면 가운데서 앞번째

 

절반만 남기고 그 안에서 찾기

줄어든 범위 내에서 재귀적으로 해결

 

한 번에 배열이 절반씩 줄어들기 때문에 시간복잡도는 O(log n)

재귀방식 or while 반복문 사용 가능

 

 

이분탐색 응용 parametric search

최적화 문제를 결정 문제로 바꾸어 푸는 것

최적화 문제 : f(i) = 1 이 되는 i 의 최솟값을 구하여라. 

결정 문제 : 어떤 i 에서, f(i) = 1 인가?

 

이분탐색 문제들

https://www.acmicpc.net/workbook/view/9764

 

백준 1920 수 찾기

백준 10816 숫자 카드 2

백준 1654 랜선 자르기 - 최댓값 구하기

백준 2805 나무 자르기 - 최댓값 구하기

 

 

 

---

참고 : 

이분탐색과 그 응용(parametric search) : https://www.youtube.com/watch?v=F6lKjRDlOpk

이분탐색 헷갈리지 않게 구현하기 : https://www.acmicpc.net/blog/view/109

이분탐색 응용 parametric search : https://www.crocus.co.kr/1000