Binary Search

Today, let’s look at LeetCode problem 875: Koko Eating Bananas. The instructions are as follows: Koko loves to eat bananas. There are n piles of bananas, the \(i\)-th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return. Return the minimum integer k such that she can eat all the bananas within h hours. ...

Very quick post about finding the peak element in an array. This is LeetCode problem 162. We have an array nums with \(n\) integers and want to find the index of one of its peaks in \(O(\log n)\) time. The important detail is this: no two neighboring elements have the same value. Let’s dive in! Solution To solve this in logarithmic time, we will use binary search. We start with a left index and a right index. We then compute a mid point mid = (left + right) / 2. Now we investigate what the local behavior around mid is. If nums[mid] > nums[mid + 1], it means that there’s no point searching for the peak at mid + 1 or to its right, so we set right = mid. Otherwise, there’s no point in searching for the peak at mid or to its left, so we set left = mid + 1. ...