Relearning Binary Search
Recently I've been learning data structure and algorithm. Having only taken one semester of it in college, I haven't had much experience in this. I picked up many different topics, some that I already knew, some completely new to me  hashmap, set, tree, merge sort, quick sort, dynamic programming, sliding window, binary search, graph, disjoint set, union find, topological sort, etc.
One of the topic that I learned in the school is Binary Search. It's pretty intuitive to remember. Say you have a sorted list of numbers:
[1,2,3,4,5,6,7,8]
You are asked to find a target number, say 3
.
Brute force, O(n)
The easiest way is to make a simple loop and compare them 1 by 1.
Check the 1st number, is it 3
?
[1,2,3,4,5,6,7,8]
^
Not found, check the 2nd number, is it 3
?
[1,2,3,4,5,6,7,8]
^
Not found, check the 3rd number, is it 3
?
[1,2,3,4,5,6,7,8]
^
Found!
In the worst case, this will take O(n)
time, since we have to loop through the number if the target is the largest number in the list: 9
.
Binary Search, O(log(n))
A simpler approach would be to eliminate half of the list every time we make a check.
Let's say we wanted to check if 7
is in the list. We start by checking with the middle element of the list.
[1,2,3,4,5,6,7,8]
^
Since 5
is smaller than 7
, we can elimate everything before 5
since this list is sorted.
[x,x,x,x,x,6,7,8]
Then we repeat the same thing until we find the target number, everytime eliminating half of the list everytime.
Due to this the time complexity will become improve from O(log(n))
instead of O(n)
.
Searching More Than A Number
Up to this point, I'm showing some pretty typical usage of binary search, the basic concept is by halving search pool everytime. But when I stumbled upon this question while crunching through LeetCode: https://leetcode.com/problems/searchinrotatedsortedarray/ (medium difficulty). This question is about searching a number in a sorted array, nothing too different from the question I just solved above. Except that the array is randomly rotated at a certain point. So the array actually looks like:
[7,8,0,1,2,3,4,5,6]
^ pivoted here
So if I can just find the point of pivot, I can perform the same binary search.
My intuition told me that I can just make a simple loop to find the pivot point. That is by checking 7, 8
, then 8,0
... Pair by pair until I find a drop in the pair, then I will know that it's the pivot point. That will make the bottle neck of the search to become O(n)
.
After reading the discussion section in LeetCode, I notice that Binary Search can actually be used to find the pivot point too! 😮
To revisit the basic concept of binary search, that is to ask the question:
"Can we eliminate half of the list everytime we make a search?"
The answer is actually yes!
Let's take a look at how we solve this example using binary search:
First, we start with checking the middle point
[7,8,0,1,2,3,4,5,6]
^
Since we are not finding a single number, that's no target
for us to check against. So let's think about what do we actually wanted to check for. If we draw the numbers into a graph:
x
x
x
x
x
x
x
x
x
[7,8,0,1,2,3,4,5,6]
You can see that from 0
to 6
we it's always increasing, what we want to find it's a decrease. Our target
is to find the decrease from 8
to 0
.
We can do this check, cut the array by half, let's call it m
, which stands for mid
.
[7,8,0,1,2,3,4,5,6]
^ ^ ^
m
We will eliminate the half of the array that is increasing, from m + 1
, we know that it's increasing, so let's eliminate that area. New array looks like this:
[7,8,0,1,2,x,x,x,x]
Now, let's do the same:
[7,8,0,1,2,x,x,x,x]
^ ^ ^
m
m + 1
is greater than m
, eliminate those that is increasing, new array becomes:
[7,8,0,x,X,x,x,x,x]
Repeat the same:
[7,8,0,x,x,x,x,x,x]
^ ^ ^
m
Now we have found it! m
is actually larger than m + 1
, it's decreasing! So we have found our index
of the pivot to be 2
.
More similar questions
There are a few variants of this question:

https://leetcode.com/problems/peakindexinamountainarray/ (easy difficulty)
 This questions is for finding the peak of a mountain array, where a mountain array is one that is increasing and then decreasing, for example:
[0,1,2,3,2,1,0]
or[1,3,7,8,1]
.
 This questions is for finding the peak of a mountain array, where a mountain array is one that is increasing and then decreasing, for example:

https://leetcode.com/problems/findinmountainarray/ (hard difficulty)
 This questions is a followup on the previous question, where not only to find the peak of a mountain, but to also find the exact
target
in a mountain type array.
 This questions is a followup on the previous question, where not only to find the peak of a mountain, but to also find the exact

https://leetcode.com/problems/findpeakelement/ (medium difficulty)
 This question is about finding any peak in an unsorted array.
Arming with a knowledge I obtained from finding the pivot
point in a rotated array, I manage to solve these similar variants of the question.
Use of Binary Search Hidden in Plain Sight
Interestingly, I thought I knew all about binary search while solving diffirent variants of the question, but I stumbled upon yet another question solvable using binary search, yet disguised as a Dynamic Programming question.
👇
https://leetcode.com/problems/splitarraylargestsum/ (hard difficulty)
Here's a brief description of the question (I'll use normal English) 
Given an unsorted array
like [7,2,5,10,8]
, it can be divided into m
. Let's say m
is 2
, it can be divided into [7] & [2,5,10,8]
or [7,2] & [5,10,8]
or so on...
Divide it in a way that the largest sum of each subarray is the smallest. From the above example case, let's list down all the different ways we can split the array:

[7] & [2,5,10,8]
, sum is7 & 25
 largest sum of this subarray =
25
 largest sum of this subarray =

[7,2] & [5,10,8]
, sum is9 & 23
 largest sum of this subarray =
23
 largest sum of this subarray =

[7,2,5] & [10,8]
, sum is14 & 18
 largest sum of this subarray =
18
 largest sum of this subarray =

[7,2,5,10] & [8]
, sum is24 & 8
 largest sum of this subarray =
24
 largest sum of this subarray =
[7,2,5] & [10,8]
is the answer, since 18
is the largest sum of the subarray that is the smallest.
Initially when I looked at the problem, it looks like a dynamic programming problem. Since it can be solved recursively. It can indeed be solved this way, but not the most efficient one. The best solution is actually binary search.
Using Binary Search
Let's try to apply Binary Search to this problem. First we need to model the question into 'Binary Searchable'. We need this few things to get started:
 lower boundary
 upper boundary
 able to cut the search pool by half
 able to check the target easily
Let's consider [7,2,5,10,8]
.
 lower boundary
The lowest sum that be produced is when we cut it into the smallest size, whenm = length
. That will bem = 5
. Whenm = 5
, the array becomes[7],[2],[5],[10],[8],
. The smallest largest sum would be10
, that will be the lowest bound.  upper boundary
The upper bound can be produced whenm = 1
, that will be[7,2,5,10,8]
and the sum is32
.  & 4.
This two points can be done together. Now we have to find a number between the lower to the upper bound. Range:10..32
. We can start at the middle,mid = 21
. In our questionm = 2
, so we can test if we can make21
withm = 2
. We can start adding up from the beginning, and make the cut when it is larger than21
. That will result in[7,2,510,8]
andm
is still not larger than2
, so it's valid. So we cut the range by half, new range:10..21
.
Now we repeat, mid = 15
, check if it's valid by adding up from the beginning. [7,25,108]
, m
has to be at least 3
to make it happen. So I change the lower bound, the new range: 15..21
.
If I keep doing this, eventually we will reach the answer 18
!
As we can see, we are cutting the search pool half and half each time, and that is binary search!
I'm still curious how other people can spot patterns like this, but I supposed it only comes with experience after doing more questions. 😆
Hope you enjoy the post, see you next time! 👋
Clap to support the author, help others find it, and make your opinion count.