HARD LESSONS, REAL TIPS

Categorize Binary Search Questions

Binary Search Questions Complete Summary

Photo by Han Lahandoe on Unsplash

Note: All the questions mentioned in this blog refer to the questions on Leetcode.

Introduction:

This blog post is not intended to mention questions that are obviously binary-search questions, like — #33 Search in Rotated Sorted Array. This blog post is to categorize questions like — #875 Koko eats Banana, which the binary search method might not be obvious at the first glance.

For those questions, the most difficult part is to figure out — what are you (binary) searching for? Some of them can directly return the binary searched result while others are a little trickier.

I often had the wrong intuition when it comes to this part. Therefore, I pulled many of these questions out and group them together to study their wordings, and to understand why and how others identify the key. Hope this is helpful to you as well.

Here is how I structure the following content:

Question number on Leetcode: Question Tittle (Difficulty Level)

the wording of the return statement statement. Bold part is the key to understand why this question is Type 1 or Type 2. 
# the logic and the steps
# to solve the question
# (some twists in the question)

Type 1: Directly Guess the Answer

All the questions below are the questions that can directly :

return the_binary_search_result

Pay careful attention to the wordings of these questions. The wordings in these questions are either — find THE x number, or the return statement requires only 1 dimension. If you don’t get why they are 1 dimensional, you can scroll down and compare them with Type-2 questions wordings.

1608. Special Array With X Elements Greater Than or Equal X (Easy)

“Return x if the array is …”
# directly guess x
# count the nums >= x

1802. Maximum Value at a Given Index in a Bounded Array (Medium)

“Return nums[index] of the constructed array…”