#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/koko-eating-bananas-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/fundamental-algorithms/binary-search/koko-eating-bananas-implementation

Repovive

Koko Eating Bananas - Implementation - Binary Search | Fundamental Algorithms | Repovive

Repovive.

Fundamental Algorithms8 sections · 294 units2h total

Open in Course

Koko Eating Bananas - Implementation

Here is the implementation:

function minEatingSpeed(piles, h):
    left = 1
    right = max(piles)

    while left < right:
        mid = (left + right) / 2
        hours = hoursNeeded(piles, mid)

        if hours <= h:
            right = mid
        else:
            left = mid + 1

    return left

function hoursNeeded(piles, speed):
    total = 0
    for pile in piles:
        total += ceil(pile / speed)
    return total

Binary search is $O(\log M)$ where $M = \max(piles)$ . Each feasibility check is $O(n)$ . Total: $O(n \log M)$ time.