C++ 이진탐색 응용

이진 탐색을 배웠다. 

이진탐색은 이미 정렬되어 있는 수를 찾는데 유용하다. 

즉 자연수는 이미 정렬 되어 있다. !!!!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ....

어떤 특정 조건에 맞춰서 값을 찾는 것이다. 

만약 특정 N^2 의 값을 찾기 위함이라면 

반복문을 통해서 넣어 봐도 되지만 이진 탐색을 통해서 하면은 O(logN) 까지 줄어 들게 된다. 

public static int squareRootBSearch(int n) {
    int min = 0;
    int max = n;
    int guess;

    while (min <= max) {
        guess = (min + max) / 2;
        if (guess * guess == n)
            return guess;
        else if (guess * guess > n)
            max = guess - 1;
        else
            min = guess + 1;
    }
    return -1;
}

if 

n= 2

1 2 3 4 5 6 7 8 9 10

중간 값을 5 이므로

중간값 ^2  을 해서 만약에 주어진 값보다 크면

25가 된다 그러면 n^2 인 4보다는 크게 되므로 왼쪽에 답이 있을 확률이 있다. 

그래서 right = mid -1 을 넣고 ( 이미 중간 값은 guess * guess == n 에서 비교 했다. ) 

1 2 3 4 5 에서 찾아보고 

이런식으로 

값을 찾는 것이다. 단지 조건만 달라 진것이다. 

원래 이진 탐색은 

1 3 5 7 9 11 13 15 17 

에서 15를 찾기 위해서  조건이 n == mid 가 되는 것 이었다. 

조건만 달라 졌을 뿐이다. 

-----------------------------------------------------------------------------

Programmers 모의고사 2번 

가로등

길이가 l인 도로에 가로등이 여러대 놓여 있습니다. 전체 도로를 밝히기 위해 좌/우 각각 d만큼을 밝히는 전구를 사려고합니다. 이때 d 값이 충분히 크다면 전체 도로를 밝게 비출 수 있지만, d 값이 작다면 일부 도로는 빛이 닿지 않습니다.

도로 길이 l과 가로등의 위치 v가 주어졌을 때, 도로를 모두 밝히는 d 값 중 최솟값을 구해주세요.

시간 복잡도를 고려해 최적값을 찾아낼 수 있는지 물어보는 문제입니다. 시간 복잡도를 고려하지 않고 나이브하게 풀었다면 효율성 테스트케이스를 맞추지 못했을겁니다.

권장 Timecomplexity: O( nlogn )

▼ 정답 예시(소팅 & 그리디) - O( nlogn )

def solution(l, v):
    v.sort()
    ans = max(v[0], l - v[-1])
    for i in range(1, len(v)):
        ans = max(ans, (v[i] - v[i-1] + 1)//2)
    return ans

▼ 정답 예시(이분탐색) - O( nlogn )

def solution(l, v):    
    n = len(v)
    answer = l
    v.sort()

    left, right = 0, l
    while(left <= right) :
        mid = (left + right) // 2

        # 맨 앞 가로등과 맨 뒤 가로등이 도로의 양 끝을 밝히는지 확인
        if v[0] - mid > 0 or v[n-1] + mid < l :
            left = mid + 1
            continue

        # 나머지 가로등으로 이분 탐색
        flag = False
        for i in range(1, n) :
            if v[i-1] + mid < v[i] - mid :
                flag = True
                break
        if flag :
            left = mid + 1
        else :
            answer = mid 
            right = mid - 1
    return answer

출처: https://programmers.co.kr/competitions/92/%EA%B3%B5%EC%B1%84-%EB%8C%80%EB%B9%84-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%8B%A4%EC%A0%84-%EB%AA%A8%EC%9D%98%EA%B3%A0%EC%82%AC-2%ED%9A%8C