Skip to main content
Code ScholarsCodeScholars

Arrays, Strings, and Pattern Techniques · Searching

Binary Search

Binary search repeatedly halves a sorted search space, but only works when the preconditions and bounds are handled carefully.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

We spend extra time on invariants because most binary-search bugs are boundary bugs.

Guided Lesson Notes

Understanding Binary Search

Binary Search focuses on contiguous sequences, index movement, and the state that can be reused while scanning. Binary search repeatedly halves a sorted search space, but only works when the preconditions and bounds are handled carefully.

Model: picture the input as boxes with numbered positions; every algorithm decision should say which positions are being read, updated, skipped, or remembered.

Invariant: the variables beside the array must summarize exactly the part of the array that has already been processed.

Implementation: careful loops, boundary checks, and small helper variables for sums, counts, positions, or best answers.

Use Binary Search when the problem asks about a subarray, substring, range, pair, frequency, or a condition over consecutive values.

Visual Model

A small picture for Binary Search

i=0

4

i=1

1

i=2

7

i=3

2

i=4

5

i=5

9

i=6

3

i=7

6

Array and string techniques usually become clear when each index has a job: scan, compare, count, enter a range, leave a range, or store a best answer.

Key Ideas

  • Sorted precondition
  • Low, high, and mid updates
  • Loop termination

Practice Prompts

  • Implement iterative binary search with tests for edge positions.
  • Use binary search to find the first value meeting a condition.

Vocabulary

Terms students should be able to say clearly

Index

The numeric position used to access an item directly.

Window

A contiguous section of the array or string currently being considered.

Prefix

Information accumulated from the start of the sequence up to a position.

Boundary

The first or last valid position included in the current scan.

State

The running information kept while the loop moves.

Invariant

The rule that makes the running state trustworthy after each iteration.

Worked Example

Worked example: tracing Binary Search

Trace a small input, focusing on sorted precondition.

  1. 1Write a small input where Binary Search is clearly useful.
  2. 2Label the part of the input related to Sorted precondition.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Indexed accessO(1)Direct index lookup is fast when the position is known.
Full scanO(n)Most search, count, and validation tasks inspect each item once.
Middle insert/deleteO(n)Items often need to shift to keep order.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Binary Search interview problem: Minimum Shipping Capacity

Interview medium

Problem

Given package weights in order and a number of days, find the smallest ship capacity that can deliver all packages within that many days.

Input

The first line contains n and days. The second line contains n package weights.

Output

Print the minimum feasible capacity.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10

Sample Output

15

Why the sample works

Capacity 15 can ship the packages in 5 days, and no smaller capacity can do it.

Approach

  1. 1The answer is between the heaviest package and the total weight.
  2. 2Binary search that capacity range.
  3. 3For each capacity, simulate loading packages in order and count days used.
  4. 4If the capacity works, search lower; otherwise search higher.

O(n log S) time and O(1) extra space, where S is the total weight range.

Java Solution

import java.util.*;

public class Main {
  static boolean canShip(int[] weights, int days, int capacity) {
    int used = 1;
    int load = 0;

    for (int w : weights) {
      if (load + w > capacity) {
        used++;
        load = 0;
      }
      load += w;
    }

    return used <= days;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int days = sc.nextInt();
    int[] weights = new int[n];

    int low = 0;
    int high = 0;
    for (int i = 0; i < n; i++) {
      weights[i] = sc.nextInt();
      low = Math.max(low, weights[i]);
      high += weights[i];
    }

    while (low < high) {
      int mid = low + (high - low) / 2;
      if (canShip(weights, days, mid)) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }

    System.out.println(low);
  }
}

Python Solution

n, days = map(int, input().split())
weights = list(map(int, input().split()))

def can_ship(capacity):
    used = 1
    load = 0
    for w in weights:
        if load + w > capacity:
            used += 1
            load = 0
        load += w
    return used <= days

low, high = max(weights), sum(weights)
while low < high:
    mid = (low + high) // 2
    if can_ship(mid):
        high = mid
    else:
        low = mid + 1

print(low)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Binary Search: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler