• Core concept with dry run

• Binary Search patterns:

  • Classic binary search

  • Binary search in rotated sorted array

  • Peak element

  • Binary Search on answers

• For Binary Search on Answers, I’ve also expanded the explanation as per your requested structure.

Binary Search — Notes & Patterns

Core Concept of Binary Search

Binary Search is an efficient algorithm used to find a target value in a sorted array by repeatedly dividing the search space in half.

Requirements:

• The data must be sorted (ascending or descending)

Process:

1. Start with left = 0 and right = n - 1

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

3. Compare arr[mid] with the target:

   • If equal → return mid

   • If less → search right half

   • If greater → search left half

Time Complexity:

• Best: O(1)

• Average and Worst: O(log n)

Space Complexity:

• Iterative: O(1)

• Recursive: O(log n) (due to stack frames)

Dry Run

Input: arr = [1, 3, 5, 7, 9], target = 7

• left = 0, right = 4

• mid = 2 → arr[2] = 5 < 7 → search right

• left = 3, right = 4

• mid = 3 → arr[3] = 7 → found at index 3

Java Code — Classic Binary Search

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Binary Search Patterns

1. Rotated Sorted Array

Problem:

Search for a target in a rotated sorted array like [4,5,6,7,0,1,2].

Key Observations:

• One half of the array is always sorted.

• Determine which half is sorted and whether the target lies in that half.

Java Code:

int searchRotated(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) return mid;

        if (nums[left] <= nums[mid]) { // left half sorted
            if (nums[left] <= target && target < nums[mid])
                right = mid - 1;
            else
                left = mid + 1;
        } else { // right half sorted
            if (nums[mid] < target && target <= nums[right])
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    return -1;
}

2. Peak Element in Unsorted Array

Problem:

Find a peak element (greater than neighbors) in an unsorted array.

Logic:

• If arr[mid] < arr[mid + 1], then peak lies on the right

• Else, peak is on the left or mid

Java Code:

int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] < nums[mid + 1])
            left = mid + 1;
        else
            right = mid;
    }
    return left;
}

3. Binary Search on Answers (Parametric/Binary Search on Feasibility)

Used when:

• The array is not necessarily sorted

• The problem is not to find an index but to minimize or maximize an answer

• You can validate whether a given value (mid) is a valid solution using a feasibility function

Step-by-Step Framework

Step 1: Try to Figure Out the Range

• Determine lower bound (low) and upper bound (high) of the answer

• These are not indices, but values within which the answer must lie

Example (Ship packages within D days):

• Min capacity = max of weights (because at least one package must fit)

• Max capacity = sum of all weights (all in one day)

int low = Arrays.stream(weights).max().getAsInt();
int high = Arrays.stream(weights).sum();

Step 2: Validate the Range

Define a feasibility function that answers:

Can we ship with a given capacity in <= D days?

boolean isFeasible(int[] weights, int D, int cap) {
    int days = 1, currentLoad = 0;
    for (int w : weights) {
        if (currentLoad + w > cap) {
            days++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    return days <= D;
}

Step 3: Run Binary Search on the Range

• Do not search for an index

• Instead, search for minimum value that passes the feasibility test

int shipWithinDays(int[] weights, int D) {
    int low = Arrays.stream(weights).max().getAsInt();
    int high = Arrays.stream(weights).sum();
    while (low < high) {
        int mid = (low + high) / 2;
        if (isFeasible(weights, D, mid)) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
}

Step 4: What to Compute Around mid

At each step, we check:

• Is mid a feasible solution?

  • If yes, then we try to find a smaller value → high = mid

  • If no, then we need a bigger value → low = mid + 1

This leads us to the smallest valid value

Step 5: Why the Compute Function is Monotonic

A function is monotonic if it is:

• True for all values >= some value (non-decreasing)

• Or False for all values <= some value (non-increasing)

In this case:

• If cap = 20 is sufficient → then cap = 21, 22, ... will also be sufficient

• Hence, isFeasible(cap) is monotonic → true after a point

This is key to apply binary search on values

Other Common Problems Using BS on Answers:

Summary of Patterns