NeetCode 15번 알고리즘 : Search Range

Search Array와는 다르게 배열이 주어지는 것이 아닌 어떠한 수의 범위가 주어진다. 

이 때, 어떠한 값을 guessing한다고 했을 때 binary search를 사용하면 된다. 

그 값이 맞는지에 대해서는 def isCorrect 함수가 black box로 존재하며, 상황에 맞게 isCorrect 함수를 내가 설정하면 된다. 

 

Code

# Binary search on some range of values
def binarySearch(low, high):

    while low <= high:
        mid = (low + high) // 2

        if isCorrect(mid) > 0:
            high = mid - 1
        elif isCorrect(mid) < 0:
            low = mid + 1
        else:
            return mid
    return -1

 

# isCorrect 예시
def isCorrect(n):
    if n > 10:
        return 1
    elif n < 10:
        return -1
    else:
        return 0

 

Example

https://neetcode.io/problems/eating-bananas

class Solution:
    def minEatingSpeed(self, piles, h):
        L, R = 1, max(piles)
        current_h = 0
        while (L<=R):
            mid = (L+R) // 2
            result = self.isTimeEnough(piles, mid,h)
            if result == 1:
                L = mid + 1 
            else :
                R = mid - 1
                current_h = mid
        return current_h
    def isTimeEnough(self, piles, number,h):
        hours = 0
        for pile in piles :
            hours += int(pile/ number) + (pile % number > 0) 
        if hours > h :
            return 1 
        else : 
            return 0