Nobody stores an array of eating speeds. There is no sorted list of ship capacities. And yet both problems are binary search, and recognising that is the single highest-leverage thing in this whole series — because once you see it, a large family of “find the minimum X such that Y” problems stops being a family and becomes one template. This is the third of three posts on Joseph Choi’s binary search session deck. Part one covered the ten problems where a sorted array supplies the predicate; part two removed the sorting and replaced it with local comparisons and reference READ MORE
Tag: binary search
Binary Search Without a Sorted Array: Peaks and Rotations in C++
Every binary search in part one had a sorted array underneath it. Take that away and most people assume the technique goes with it. It does not — sortedness was never the requirement, only the most convenient way to meet it. This is the second of three posts on Joseph Choi’s binary search session deck. Seven problems here, in two families: three where the array rises and then falls, and four where a sorted array has been rotated. In both, something other than the sort order tells you which half to keep. As in part one, every listing was compiled READ MORE
Binary Search in C++: The Boundary Template and 10 Sorted-Array Problems
Binary search is the algorithm everyone knows and almost nobody writes correctly on the first try. The reason is not the idea, which is two lines. It is that every failure mode is silent: no crash, no timeout, just a wrong index. This is the first of three posts working through Joseph Choi’s binary search session deck in C++. Between them they cover twenty-two LeetCode problems, and they are split by the only question that matters — where does the monotonicity come from? This post takes the ten problems where it comes from the sort order, and sets up the READ MORE
Intro to Binary Search Algorithm
Let’s say there is an unsorted array and you need to find certain values.How would you search for those values? You can’t avoid iterating the entire array every time you are searching since the array is unsorted.Wouldn’t this be a very inefficient way of searching?It may be fine if the size of the array is pretty small. However, what if there are one million elements in the array?You probably do not want to iterate one million elements every time you search because it’s a waste of time. Binary search algorithm is a very efficient search algorithm.It requires the array to READ MORE