M.T.Ramkrushna

Posted on Sep 14

DSA: Topic 5: Binary Search

#algorithms #beginners #computerscience #interview

Interview frequency: ⭐⭐⭐⭐⭐

Most beginners think Binary Search is just:

"Find an element in a sorted array."

In reality, that's only 10% of its interview usage.

Most interview questions use Binary Search on the Answer.

What Interviewers Want

When interviewers ask a Binary Search question, they're testing whether you can recognise:

A sorted search space.
A monotonic condition (once something becomes true, it stays true—or vice versa).
How to reduce a search from O(n) to O(log n).

Part 1: Classic Binary Search

Suppose you have:

nums = [2, 5, 8, 10, 15, 20, 30]
target = 15

Instead of checking each element:

2 → 5 → 8 → 10 → 15

Binary Search repeatedly cuts the search space in half.

2 5 8 10 15 20 30
      ↑
     mid

If:

nums[mid] == target

You're done.

If:

nums[mid] < target

Discard the left half.

If:

nums[mid] > target

Discard the right half.

Code

def binary_search(nums, target):
    left = 0
    right = len(nums) - 1

    while left <= right:

        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        elif nums[mid] < target:
            left = mid + 1

        else:
            right = mid - 1

    return -1

Complexity:

Time : O(log n)

Space: O(1)

Why is it O(log n)?

Imagine:

1,000,000 elements

Linear Search

Worst case

1,000,000 comparisons

Binary Search

1,000,000

↓

500,000

↓

250,000

↓

125,000

↓

...

Only about 20 comparisons.

That's why it's so powerful.

Interview Trick #1

The array must be sorted.

If it isn't:

Don't immediately think Binary Search.

Part 2: First and Last Occurrence

Example

[1,2,2,2,2,3,4]

Find the first occurrence of 2.

Normal Binary Search might return:

index = 3

Wrong.

Expected:

index = 1

Interview trick:

When you find the target,

don't stop.

Continue searching the left half.

Similarly,

for the last occurrence,

continue searching the right half.

Part 3: Lower Bound & Upper Bound

Many companies ask this.

Example

nums = [2,4,4,4,8]

Lower Bound of 4

First position ≥ 4

Answer

Upper Bound

First position > 4

Answer

Part 4: Binary Search on the Answer ⭐⭐⭐⭐⭐

This is where interviews become interesting.

Suppose the interviewer asks:

Koko eats bananas.

Find the minimum eating speed.

The array is not sorted.

Can we still use Binary Search?

Yes.

Because the answer space is sorted.

Possible speeds:

Suppose:

Speed = 3

Impossible

Speed = 4

Possible

Speed = 5

Possible

Speed = 6

Possible

Notice the pattern.

False False False True True True

This is called a monotonic condition.

Binary Search works because once it becomes True, it stays True.

How to Recognise Binary Search on the Answer

Ask yourself:

Am I searching for the minimum or maximum value that satisfies a condition?

Examples:

Minimum speed
Minimum capacity
Maximum distance
Smallest feasible answer

These are strong hints.

Generic Template

left = minimum_possible_answer
right = maximum_possible_answer

while left < right:

    mid = (left + right) // 2

    if is_possible(mid):
        right = mid
    else:
        left = mid + 1

return left

This template appears in many interview problems.

Common Interview Mistakes

Mistake 1

Using:

mid = (left + right) // 2

This is fine in Python because integers don't overflow, but in languages like Java or C++, interviewers often expect:

mid = left + (right - left) // 2

It's a good habit across languages.

Mistake 2

Wrong loop condition

Many candidates write:

while left < right

when they should use

while left <= right

Know which variant you're implementing.

Mistake 3

Updating the wrong pointer.

Remember:

Target is larger

↓

Move left

Target is smaller

↓

Move right

Real Interview Questions

Easy

Binary Search ⭐⭐⭐⭐⭐
Search Insert Position ⭐⭐⭐⭐

Medium

First & Last Position ⭐⭐⭐⭐⭐
Search in Rotated Sorted Array ⭐⭐⭐⭐⭐
Find Minimum in Rotated Sorted Array ⭐⭐⭐⭐
Peak Element ⭐⭐⭐⭐

Binary Search on Answer

Koko Eating Bananas ⭐⭐⭐⭐⭐
Capacity to Ship Packages Within D Days ⭐⭐⭐⭐⭐
Split Array Largest Sum ⭐⭐⭐⭐⭐
Aggressive Cows (very popular in competitive programming and some interviews) ⭐⭐⭐⭐

Interview Checklist

When you read a question, ask:

Is the data already sorted?

If yes → Consider classic Binary Search.

Am I searching for a minimum or maximum feasible value?

If yes → Think Binary Search on the Answer.

Does the condition change only once?

Example:

 False False False True True True

 True True True False False

If yes → Binary Search is likely applicable.

Summary of Topics Covered

Topic	Interview Frequency	Key Idea
Arrays	⭐⭐⭐⭐⭐	Traversal and manipulation
Hash Maps & Sets	⭐⭐⭐⭐⭐	Fast lookups and counting
Two Pointers	⭐⭐⭐⭐⭐	Efficient pair and in-place problems
Sliding Window	⭐⭐⭐⭐⭐	Contiguous subarrays/substrings
Binary Search	⭐⭐⭐⭐⭐	Search efficiently in sorted or monotonic spaces

These five topics form the foundation of a large portion of coding interview problems. The next topic is Stacks & Monotonic Stacks, another extremely common interview pattern used for problems like Valid Parentheses, Daily Temperatures, Next Greater Element, and Largest Rectangle in a Histogram.

DEV Community