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

이분 탐색이란 ?

정렬된 배열에서 원하는 값의 존재 여부 및 위치를 찾는 알고리즘으로 탐색할 때마다 검사 범위가 절반으로 줄어듭니다.

시간 복잡도 : O(log N)

 

이분 탐색 과정

1. 검사 범위에서 중간 값(mid)를 선택해 찾고자 하는 값(target)이 같은지 확인

2. 찾고자 하는 값이라면 해당 값 반환

3. 찾고자 하는 값보다 작다면 (mid < target), low = mid + 1

4. 찾고자 하는 값보다 크면 (mid > target), high = mid - 1

5. 1 ~ 4번을 (low <= high)동안 반복

 

예시

백준 2805 나무자르기 

나무의 수 N과 나무의 길이 M이 주어질 때, M미터 나무를 집에 가져가기 위해 설정할 수 있는 높이의 최댓값을 출력하는 문제

 

ex. 4 7

      20 15 10 17

1. 나무 길이 오름차순 정렬 : t[4] = [10, 15, 17, 20]

2. 이분 탐색을 통해 가져갈 수 있는 나무길이 H 갱신

   

    low = 0
    high = t[t.size()-1];
	while(low <= high) {
       	ll mid = (low + high) / 2;
        H = 0;
        for (int i = 0; i < N; i++) {
            if (t[i] - mid > 0) {	// 자를 수 있는 경우
                H += t[i] - mid;	// 집에 가져가기
            }
        }
        if (H >= M) {	// 집에 가져가려하는 길이 M보다 큰 경우
            ans = mid;
            low = mid + 1;	// 덜 가져가야하므로 더 크게
        }
        else {	// 반대의 경우
            high = mid - 1;	// 더 가져가야하므로 더 작게
        }
    }

 

---

참고

https://m42-orion.tistory.com/69