Backend interview prep

Start

Binary Search Pattern - Java Coding Interview Guide

Master the Binary Search pattern in Java with intuition, internal working, search variations, Java implementation, production use cases, complexity analysis, common mistakes, and interview questions.

Introduction

The Binary Search Pattern is one of the most fundamental and frequently tested coding interview patterns.

Instead of checking every element one by one, Binary Search repeatedly eliminates half of the search space, reducing the time complexity from O(n) to O(log n).

This pattern extends far beyond searching sorted arrays. It is widely used in optimization problems, monotonic functions, rotated arrays, and answer-space searching.

When Should You Use Binary Search?

Use this pattern when:

  • The data is sorted.
  • The search space is monotonic.
  • You need the minimum or maximum valid answer.
  • Half of the search space can be discarded.
  • The problem asks for logarithmic performance.

Typical interview keywords include:

  • Search
  • Sorted
  • Minimum
  • Maximum
  • Lower Bound
  • Upper Bound
  • Capacity
  • Speed
  • Threshold

Basic Idea

Binary Search repeatedly divides the search space into two halves.

graph TD
    Search_Space["Search Space"] --> Find_Middle["Find Middle"]
    Find_Middle["Find Middle"] --> Target_Found["Target Found?"]
    Target_Found["Target Found?"] --> No["No"]
    No["No"] --> Discard_One_Half["Discard One Half"]
    Discard_One_Half["Discard One Half"] --> Repeat["Repeat"]

Each iteration reduces the remaining work by half.

Visualization

Sorted Array

1 3 5 7 9 11 13

L     M      R

If the target is greater than the middle value:

Discard Left Half

↓

7 9 11 13

If the target is smaller:

Discard Right Half

↓

1 3 5

Generic Algorithm

left = 0

right = n - 1

while(left <= right)

    mid

    target found?

        return

    target smaller?

        search left

    otherwise

        search right

return not found

Java Implementation

public class BinarySearchPattern {

    public static int binarySearch(int[] nums, int target) {

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {

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

            if (nums[mid] == target) {
                return mid;
            }

            if (target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }

        return -1;
    }

    public static void main(String[] args) {

        int[] nums = {1,3,5,7,9,11};

        System.out.println(binarySearch(nums,7));

    }

}

Internal Working

Searching for

7

Array

1 3 5 7 9 11

L     M     R

Middle

5

Target is greater.

Move

Left = Mid + 1

Next

7 9 11

L M R

Target found.

Binary Search Variations

Find whether a value exists.

Lower Bound

Find the first position where a value can be inserted.

Upper Bound

Find the first element greater than the target.

First Occurrence

Locate the first duplicate.

Last Occurrence

Locate the last duplicate.

Search after array rotation.

Peak Element

Find a local maximum.

Binary Search on Answer

Search the answer space instead of the input array.

Examples:

  • Koko Eating Bananas
  • Allocate Books
  • Capacity to Ship Packages
  • Aggressive Cows
  • Split Array Largest Sum

Binary Search Decision Tree

graph TD
    Sorted_Data["Sorted Data?"] --> Yes["Yes"]
    Yes["Yes"] --> Target_Search["Target Search?"]
    Target_Search["Target Search?"] --> Standard_Binary_Search["Standard Binary Search"]
    Standard_Binary_Search["Standard Binary Search"] --> N_["-------------------"]
    N_["-------------------"] --> Boundary_Search["Boundary Search?"]
    Boundary_Search["Boundary Search?"] --> Lower_Upper_Bound["Lower / Upper Bound"]
    Lower_Upper_Bound["Lower / Upper Bound"] --> N_["-------------------"]
    N_["-------------------"] --> Optimization_Problem["Optimization Problem?"]
    Optimization_Problem["Optimization Problem?"] --> Binary_Search_on_Answer["Binary Search on Answer"]
    Binary_Search_on_Answer["Binary Search on Answer"] --> N_["-------------------"]
    N_["-------------------"] --> Rotated_Array["Rotated Array?"]
    Rotated_Array["Rotated Array?"] --> Modified_Binary_Search["Modified Binary Search"]

Complexity Analysis

Operation Complexity
Time O(log n)
Space O(1)

Each iteration eliminates half of the remaining search space.

Why Binary Search is Efficient

Linear Search

graph TD
    N_1["1"] --> N_2["2"]
    N_2["2"] --> N_3["3"]
    N_3["3"] --> n["n"]

Time Complexity

O(n)

Binary Search

graph TD
    n["n"] --> n_2["n/2"]
    n_2["n/2"] --> n_4["n/4"]
    n_4["n/4"] --> n_8["n/8"]

Time Complexity

O(log n)

Production Use Cases

Database Indexes

Locate rows using B-Tree indexes.

Search Engines

Search sorted posting lists efficiently.

Banking

Search transactions by sorted identifiers.

E-Commerce

Search products sorted by price or rating.

Cloud Resource Scheduling

Determine minimum required resources using Binary Search on Answer.

Machine Learning

Tune hyperparameters using monotonic search spaces.

Operating Systems

Locate pages and memory regions efficiently.

Network Routing

Search routing tables and optimized lookup structures.

Common Problems Using Binary Search

Problem Difficulty
Binary Search Easy
Search Insert Position Easy
First and Last Position Medium
Search Rotated Array Medium
Find Minimum in Rotated Array Medium
Find Peak Element Medium
Koko Eating Bananas Medium
Capacity to Ship Packages Medium
Median of Two Sorted Arrays Hard

Common Mistakes

Applying Binary Search to Unsorted Data

Binary Search requires sorted data or a monotonic search space.

Incorrect Middle Calculation

Wrong

(left + right) / 2

Correct

left + (right - left) / 2

Wrong Loop Condition

Use

while(left <= right)

for standard search unless a variation requires different boundaries.

Updating the Wrong Pointer

Always update the pointer corresponding to the eliminated half.

Ignoring Edge Cases

Test:

  • Empty array
  • Single element
  • Target not found
  • First element
  • Last element
  • Duplicate values

Interview Tips

Mention these observations:

  • Binary Search requires sorted or monotonic data.
  • Every iteration removes half of the search space.
  • Always explain why Binary Search is applicable before coding.
  • Mention overflow-safe midpoint calculation.
  • Recognize when a problem is actually Binary Search on Answer.

Frequently Asked Interview Questions

Answer

Binary Search is a divide-and-conquer algorithm that repeatedly divides a sorted search space into two halves until the target is found or the search space becomes empty.

Answer

The data must be sorted or the search space must have a monotonic property that allows one half to be safely discarded.

3. What is the time complexity?

Answer

  • Best Case: O(1)
  • Average Case: O(log n)
  • Worst Case: O(log n)

4. What is the space complexity?

Answer

O(1) for the iterative approach and O(log n) for the recursive approach due to the call stack.

5. Why is left + (right - left) / 2 preferred?

Answer

It prevents integer overflow that may occur with (left + right) / 2.

6. What is Binary Search on Answer?

Answer

It searches a range of possible answers instead of the input values by repeatedly testing whether a candidate answer satisfies the problem constraints.

7. Which problems commonly use this pattern?

Answer

Search Insert Position, First and Last Position, Rotated Array Search, Peak Element, Koko Eating Bananas, Allocate Books, Capacity to Ship Packages, and Median of Two Sorted Arrays.

8. Where is Binary Search used in production?

Answer

Database indexing, search engines, cloud resource optimization, scheduling systems, operating systems, networking, and machine learning optimization.

9. What is the biggest mistake candidates make?

Answer

Using Binary Search on unsorted data or failing to identify that the search space is monotonic.

10. Why is Binary Search one of the most important interview patterns?

Answer

It is simple, highly efficient, and serves as the foundation for many advanced algorithms involving optimization, searching, and monotonic functions.

Quick Revision

Topic Summary
Pattern Binary Search
Requirement Sorted or Monotonic Data
Main Idea Eliminate Half of the Search Space
Time Complexity O(log n)
Space Complexity O(1)
Key Variations Lower Bound, Upper Bound, Rotated Array, Answer Search
Interview Frequency ⭐⭐⭐⭐⭐

Key Takeaways

  • Binary Search is a foundational algorithm that reduces search complexity from O(n) to O(log n).
  • The pattern applies to sorted arrays as well as monotonic answer spaces.
  • Understanding its variations is essential for solving medium and hard interview problems.
  • Overflow-safe midpoint calculation and correct boundary updates are critical for correct implementations.
  • Mastering this pattern prepares you for advanced topics such as optimization problems, rotated arrays, and search-based scheduling challenges.