Backend interview prep

Start

Binary Search - Java Coding Interview Guide

Master Binary Search for Java coding interviews with explanation, algorithm, Java implementation, complexity analysis, variations, production use cases, common mistakes, and interview questions.

Binary Search

Java Coding Interview Track

Lesson 01

Learning Path

# Topic
01 Binary Search ←
02 Binary Search Variations
03 First & Last Occurrence
04 Search Insert Position
05 Rotated Sorted Array
06 Peak Element
07 Square Root using Binary Search
08 Binary Search on Answer
09 Median of Two Sorted Arrays
10 Time Complexity Patterns

Introduction

Binary Search is one of the most important algorithms in technical interviews. It efficiently searches for an element in a sorted collection by repeatedly dividing the search space into two halves.

Instead of checking every element like Linear Search, Binary Search eliminates half of the remaining elements after each comparison, making it significantly faster for large datasets.

It is commonly asked in interviews at companies like Amazon, Google, Microsoft, Meta, Apple, Netflix, Oracle, IBM, and many others.

What is Binary Search?

Binary Search is a divide-and-conquer algorithm.

It works only when:

  • Array is sorted
  • Search space is ordered

At each iteration:

  1. Find middle element
  2. Compare with target
  3. Ignore half of the array
  4. Continue until found

Visualization


Array

2   5   8   12   16   23   38   56   72

Target = 23


   ↓


2   5   8  12  16  23  38  56  72
Mid

23 > 16

Discard Left Half

23 38 56 72

↓


23 38 56 72
Mid

Target Found

Binary Search Algorithm


Start

↓

Find Mid

↓

Is Mid == Target ?

↓

Yes → Return Index

↓

No

↓

Target < Mid ?

↓

Search Left Half

Else

Search Right Half

Repeat

Java Implementation (Iterative)

public class BinarySearch {

    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 = {2,5,8,12,16,23,38,56};

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

    }

}

Recursive Solution

public static int binarySearch(int[] arr,
                               int left,
                               int right,
                               int target){

    if(left > right)
        return -1;

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

    if(arr[mid]==target)
        return mid;

    if(target < arr[mid])
        return binarySearch(arr,left,mid-1,target);

    return binarySearch(arr,mid+1,right,target);

}

Complexity Analysis

Operation Complexity
Best Case O(1)
Average Case O(log n)
Worst Case O(log n)
Space (Iterative) O(1)
Space (Recursive) O(log n)

Why is Mid Calculated Like This?

❌ Incorrect

int mid = (left + right) / 2;

This may overflow for very large arrays.

✅ Preferred

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

This avoids integer overflow.

When Can Binary Search Be Used?

Use Binary Search when:

  • Array is sorted
  • Searching in sorted lists
  • Finding insertion position
  • Finding first occurrence
  • Finding last occurrence
  • Searching answer space
  • Monotonic functions

Production Use Cases

Databases internally use B-Trees that rely on Binary Search concepts.

Example:

  • MySQL
  • PostgreSQL
  • Oracle

Searching a word inside a sorted dictionary.

Phone Contacts

Searching contacts alphabetically.

E-commerce

Searching products sorted by price.

Log File Analysis

Searching timestamps inside sorted logs.

Version Control

Finding first bad version.

Search Engine

Searching sorted indexes.

Binary Search Flow

Sorted Array

↓

Find Mid

↓

Target ?

↓

Left Half

or

Right Half

↓

Repeat

↓

Found

Common Interview Variations

  • Binary Search
  • Lower Bound
  • Upper Bound
  • First Occurrence
  • Last Occurrence
  • Count Occurrences
  • Search Insert Position
  • Peak Element
  • Rotated Array
  • Infinite Array
  • Binary Search on Answer
  • Koko Eating Bananas
  • Capacity to Ship Packages
  • Allocate Books

Common Mistakes

❌ Using Binary Search on unsorted array

❌ Infinite loop

while(left < right)

instead of

while(left <= right)

❌ Integer overflow

❌ Wrong boundary updates

❌ Forgetting return -1

Tips for Interviews

✅ Always ask whether the array is sorted.

✅ Mention time complexity before coding.

✅ Use iterative approach unless recursion is requested.

✅ Explain why Binary Search is O(log n).

✅ Use overflow-safe mid calculation.

Interview Questions

Answer

Binary Search is a divide-and-conquer algorithm that searches a sorted array by repeatedly dividing the search space into two halves.

2. What is the time complexity?

Answer

O(log n)

3. Why must the array be sorted?

Answer

Because Binary Search eliminates one half based on ordering.

4. What happens if the array is unsorted?

Answer

The algorithm may return incorrect results.

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

Answer

To prevent integer overflow.

Linear Binary
O(n) O(log n)
Unsorted OK Requires Sorted
Sequential Divide & Conquer

7. Can Binary Search work on Linked Lists?

Answer

No.

Random access is required.

Linked Lists require O(n) traversal.

8. When should Binary Search not be used?

  • Unsorted data
  • Small datasets where sorting cost is high

9. Recursive vs Iterative?

Iterative:

  • Faster
  • Constant space

Recursive:

  • Cleaner
  • Uses stack memory

10. What are common Binary Search interview problems?

  • First occurrence
  • Last occurrence
  • Search Insert Position
  • Rotated Array
  • Peak Element
  • Median of Two Sorted Arrays
  • Square Root
  • Binary Search on Answer

Quick Revision

Concept Value
Technique Divide & Conquer
Input Sorted Array
Best Case O(1)
Worst Case O(log n)
Space O(1)
Overflow-safe Mid Yes
Random Access Needed Yes
Interview Frequency ⭐⭐⭐⭐⭐

Key Takeaways

  • Binary Search is one of the most frequently asked coding interview algorithms.
  • It works only on sorted data and reduces the search space by half at each step.
  • The iterative implementation uses O(1) extra space and is generally preferred in interviews.
  • Always calculate the middle index using left + (right - left) / 2 to avoid integer overflow.
  • Understanding Binary Search is the foundation for solving advanced problems such as rotated arrays, peak elements, search-in-answer-space, and optimization problems.