binary search 이분 탐색

요새 코테 공부를 다시 매일 한 문제 씩 풀어나가고 있다.

프로그래머스 이분 탐색 문제도 풀면서, while l < r 을 해야할지, while l <= r을 해야할지 헷갈릴 때가 가끔 생겨서 template을 공유해보고자 한다.

---

이분 탐색의 핵심은 search space를 half로 줄이는 것이다. O(n) -> O(log N)

 

가끔 이러한 공통된 고민을 하고는 한다.

 

1. 언제 loop을 빠져나가야하는가? (left < right 혹은 left <= right 중에 무엇을 골라야하는지)

2. left와 right의 boundary는 어떻게 정해야하는가

3. boundary는 어떻게 update하는 것이 좋은가? (left = mid, left  = mid + 1, right = mid, right = mid + 1)

 

이러한 고민을 해본 적이 없는가? 솔직히 나도 해본 적이 있다.

binary search를 사람들이 사용하면서, 흔히 하는 착각 중 하나가, 정렬된 주어진 배열이 있을 때, specific한 value를 찾는 케이스에만 이 방법이 사용될 수 있다는 것이다.

 

template을 보면 더 잘 이해할 수 있다.

 

Minimize k, s.t condition(k) is True

def binarySearch(array) -> int:
	def condition(value) -> bool:
    	pass
    
    # could be [0, n], [1, n] etc. depends on problem
    left, right = min(searchSpace), max(searchSpace) 
    
    while left < right:
    	mid = left + (right - left) // 2
        
        if condition(mid):
        	right = mid
        
        else:
        	left = mid + 1
        
        return left

여기서 우리는 3가지 부분만 문제를 풀면서 해결해 나가면 된다.

- boundary variables을 옳바르게 설정할 것. 모든 possible elements를 포함하고 있는 boundary를 설정하자

- return value를 결정할 것.(return left와 return left -1 중에서 무엇을 선택할 것인가? 정답은 left이다. existing while loop을 빠져나가고 나면, left는 condition function을 만족하는 minimal k이다. -1을 해 줄 필요가 없다.)

- condition fuction을 design할 것.

 

사실 첫 번째, 세 번째 부분만 해결하면 된다. 두 번째는 대부분 고쳐야할 필요성이 적다.

 

---

준비는 끝났다. 예시 문제를 풀어보면서 끝내보자.

https://school.programmers.co.kr/learn/courses/30/lessons/43238

 

프로그래머스 입국심사 문제이다. condition을 무엇으로 잡아야할지, boundary를 무엇으로 잡아야할지 감을 처음에 잡기 어렵지만, 조금 고민해보면 된다. time spent to consume all passengers이다.

 

def solution(n, times):
    l, r = 1, max(times) * n
    
    
    while l < r:
        
        mid = l + (r - l) // 2
        cnt = 0    
        
        for time in times:
            cnt += mid // time
            
        if cnt >= n:
            r = mid 
            
        else:
            l = mid + 1    
            
    return l