# Binary Search like a Staff SWE

### Intro

Every FAANG SWE is familiar with binary search. When it is time to code, most solutions, even by senior candidates appear to be rote memorized and reproduced to find an integer (or not) in an array. These implementations are one offs and can’t be reused for other problems. This article attempts to build a generic implementation and then use this to solve multiple problems. What is better than Leetcode problems to test the correctness and efficiency of this implementation?! That’s what a FAANG Staff SWE would do! Right?

### Key Idea

I am not going to talk about binary search in great detail since by reaching until this point, you have proven you know its inner workings. If not, please consult any of the umpteen number of references on this topic available on the interwebs.

Instead I am going to talk about how an abstract binary search implementation can be written that can be applied on multiple problems.

A binary search can be parameterized with the following:

- A comparison function, that can be executed on the middle element to decide whether we have found the target element or whether we should look in left half of the search space, or the right half
- A function that gives us
`i`

th element in the list. For an array, it just gives the element at`i`

th index. - A
`startIndex`

and an`endIndex`

that set the boundaries of the list we are looking into.

With these parameters, let’s attempt to write a generic implementation of binary search.

The second overload uses a `BiFunction`

instead of a `Function`

and passes the current index of `mid`

as the second parameter
so that in certain problems `mid`

is made available to the `testFunc`

. In this pattern of problems `testFunc`

needs to check for a
condition with any of the elements adjacent to mid.

Here are the equivalent C# implementations.

Armed with this implementation, can we solve some common Leetcode problems that require binary search?

Let’s try LC 74 Search a 2D Matrix.

Wow! What was that? Driver function was just three lines (excluding the bad input check) in Java which is considered a very verbose language. That’s the magic of higher order functions :-) Submission Link

Let’s try another one. LC 69 Sqrt(x).

Let’s try LC 162 Find Peak Element.

Let’s try LC 35 Search Insert Position.

This too runs in 1ms and beats 100% of the solutions in runtime. Here’s the submission link if you want to verify.

The driver function here is slightly longer with the indexCheck method taking up a few lines. Still, the program is very easy to understand!

Let’s try LC 153 Find min in Rotated Sorted Array. This involves finding the index at which array is pivoted i.e. rotated and then returning the element at that index.

Let’s try LC 33 Search in Rotated Sorted Array. This one uses the logic for finding pivot element from the previous problem and then builds on top of that.

How about LC 981 Time Based Key-Value Store

How about LC 875 Koko Eating Bananas?

With these few examples communicating the idea, I leave it to the reader to solve other binary search problems with this generic template.

leetcode

binary-search

programming

computer-science

]