Binary Search

Binary search is a simple algo, check mid value, compare, ignore invalid half, move to the valid half until completed / element is found.
But the code has many variable, low, high, mid
Should the loop be while (low < high) or while (low <= high)?
or high = mid -1 or high = mid ;
What exactly these mean, let’s explore these item.

Considerations

• Must include all elements in search
• Low and high must shrink correctly when only two elements remain.
• Mid must be handled consistently

Pattern 1: while (low <= high)

This pattern checks every element inside the loop.
The condition low <= high means the loop continues until all elements are explicitly examined.

How it works

1. Compute mid.
2. Check if mid is the answer.
3. If the target is larger than mid, move right.
4. If the target is smaller than mid, move left.
5. Always eliminate mid using mid + 1 or mid - 1.

Every possibility is handled inside the loop, so no post-loop check is needed.

int search(vector<int> &nums, int target) {
    int low = 0, high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

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

        else if (target > nums[mid])
            low = mid + 1;

        else
            high = mid - 1;
    }

    return -1;
}

• Mid is always checked directly.
• Shrinking uses strict ±1, preventing infinite loops.
• No hidden logic before or after the loop.
• Debugging becomes straightforward because every iteration has the same structure.

This forms a strong mental model and is usually the most intuitive pattern.

Pattern 2: while (low < high)

This version stops when only one element is left unprocessed.
Because the loop condition is low < high, the loop breaks at low == high, and the final element must be checked after the loop.

Key difference

Since the last element is not checked inside the loop, the loop must maintain the invariant that the answer always remains inside the search boundary.

while (low < high) {
    int mid = low + (high - low) / 2;

    if (condition)
        high = mid;      // mid stays inside the range
    else
        low = mid + 1;   // mid is eliminated
}

return low; // check this final index separately

Why high = mid (not mid - 1)?

Take an array [0,1,2] and search for 1.
mid = 1.
If you use high = mid - 1, you eliminate the middle element incorrectly.
This breaks the invariant that the final answer must survive inside the shrinking boundary.

So, in this pattern:

• high = mid (mid included)
• low = mid + 1 (mid excluded)

high = mid - 1 must not be used.

Problems that appear easily

• Using high = mid - 1 breaks the algorithm.
• Checking mid inside the loop breaks the template.
• Forgetting the final check after the loop causes incorrect results.
• Moving low incorrectly may cause infinite loops when 2 elements remain.

This pattern works only when strictly following its rules.

Use while (low <= high) with mid checked inside the loop.

This keeps everything explicit, avoids hidden assumptions, and eliminates infinite-loop traps when the array shrinks to two elements.

Some Problems to solve (follow the order for better understanding)

704. Binary Search

https://leetcode.com/problems/binary-search/description/

We can simply use our pattern of binary search.

    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size() -1, mid;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (target > nums[mid]) {
                low = mid +1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

Implement Lower Bound

https://www.naukri.com/code360/problems/lower-bound_8165382?leftPanelTabValue=PROBLEM

For a [0,1,1,1,1,3], although first mid we found at 3, but for lower bound we need to look on left if there are more occurances or not. So, we use the same pattern and keep looking in left once mid == x (instead of returning early) , the rest of the code stays the same.

int lowerBound(vector<int> arr, int n, int x) {
        // Write your code here

        int low = 0, high = n-1,  mid, result = -1;

        while (low <= high) {
                mid = low + (high - low) /2;
                if (arr[mid] == x) {
                    result = mid;
                    high = mid - 1;
                } else if (arr[mid] > x) {
                     high = mid - 1;
                } else {
                     low = mid + 1;
                }
        }
        if ( result != -1) return result;
        return low;
}

https://leetcode.com/problems/first-bad-version/description/

[1,2,3,4,5,6,7,8,9,n]
We need to find firstBadVersion, they have already given an API, which can be called on each version. So, the basic thought could be , but it runs in o(n)

for (int i = 0; i < n ; i++) {
    bool res = isBadVersion(i);
    if (res) {
        return i;
    }
}

Let’s assume that how the versions could look like
[0,0,0,0,0,1,1,1,1,1,1]
-> 0 – Good Version
-> 1 – Bad Version
It is finding like lower_bound of 1 in the array, which we already covered before, given that here are only 2 states true, false, so we move accordingly.

    int firstBadVersion(int n) {
        // [0,0,0,0,1,1,1,1] -> first occurance of 1 , lower bound
        int low =  1, high = n, mid;
        int result = -1;
        while (low <= high) {
            mid = low + (high - low ) / 2;
            if (isBadVersion(mid)) {
                result = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return result;
    }

https://leetcode.com/problems/sqrtx/

    int mySqrt(int x) {
        if (x < 2) return x;
        long low = 1, high = x / 2, mid;
        while (low <= high) {
            mid = low + (high - low) / 2 ;
            if (mid * mid == x) {
                return mid;
            }
            if (x > mid * mid) {
                low = mid + 1;
            } else {
                high = mid -1;
            }
        }
        return low - 1; // low - 1 or high 
    }

We want floor(sqrt(20)) which is 4.

Here’s the “line of candidates” from 1 to 10 (more than enough for sqrt(20)):

1   2   3   4   5   6   7   8  ...
|   |   |   |   |   |   |   |
^---------------------------^
 low                     high

Now split them into two conceptual zones:

Left zone = numbers whose square ≤ 20
Right zone = numbers whose square > 20

Before we start we don’t know the real boundary, so low=1 and high=10 (or x/2=10).

Iteration 1

mid = (1+10)/2 = 5
Check 5² = 25 → too big.
So 5 is in the right zone → the boundary is ≤ 5.

Update: high = 4

Representation:

1   2   3   4   [5]  6  7 ...
|   |   |   |         |
^-----------^
low         high

Everything right of 4 is now known to be too big.

---

Iteration 2

mid = (1+4)/2 = 2
Check 2² = 4 → <= 20 → left zone.
So 2 is too small, boundary > 2.

Update: low = 3

1   2   [3]   4
    <---->|<---->
   left      unknown

Now we know for sure:

• 1,2 are in left zone
• 5,6,7… were already in right zone

---

Iteration 3

mid = (3+4)/2 = 3
Check 3² = 9 → <=20 → left zone.

Update: low = 4

1   2   3   [4]
            |
         low/high?

---

Iteration 4

mid = (4+4)/2 = 4
Check 4² = 16 → <=20 → left zone.

Update: low = 5

1   2   3   4   [5]
                |
                low
(high is 4)

Now loop ends because low = 5 and high = 4.

Here’s the final picture

Left zone:   1   2   3   4
Boundary →   5   (first too big)
Right zone:  5   6   7  ...

Binary search ended with:

low  = 5    ← first “too big”
high = 4    ← last “not too big”

https://leetcode.com/problems/search-insert-position/

This is the same problem, no change in the template code.

    int searchInsert(vector<int>& nums, int target) {
        int low = 0, high = nums.size() - 1, mid;
        while (low <= high) {
            mid = low + (high - low ) / 2 ;
            if (target == nums[mid]) {
                return mid;
            }
            if (target > nums[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/

When you first see this problem, nothing screams “binary search.” It looks like a scheduling issue: just load packages until you overflow and move to the next day. But the trick is to step back and treat the ship capacity itself as the thing we search for.

The question wants the minimum ship capacity that can finish all packages in exactly D days. Let’s start with the brute-force reasoning. A ship must at least carry the heaviest package, so the minimum possible capacity is max(weights). And if we wanted to finish everything in one day, the capacity would need to be the sum of all weights.

For the example:

weights = [1,2,3,4,5,6,7,8,9,10]
days = 5

We get:

min capacity = 10
max capacity = 55

So capacity must lie somewhere in the range:

10, 11, 12, 13, ..., 55

Now imagine testing each capacity and computing how many days it needs. For a few capacities, the behavior looks like this:

Capacity | Days taken
-----------------------
10       | 7
11       | 6
12       | 6
13       | 6
14       | 6
15       | 5   ← first capacity that meets target days
16       | 5
...

This is the key observation: as capacity increases, the number of days never increases. It only stays the same or drops. This monotonic relationship lets us switch from “try everything” to binary search. We’re essentially solving a lower-bound problem:
find the smallest capacity such that days <= targetDays.

The simulation for “how many days does a given capacity require” is simple: accumulate weights until the next package would overflow; when it does, start a new day.

int daysForCap(vector<int>& weights, int cap) {
    int days = 0, sum = 0;
    for (int w : weights) {
        if (sum + w > cap) {
            days++;
            sum = 0;
        }
        sum += w;
    }
    return days + 1;
}

int shipWithinDays(vector<int>& weights, int target) {
    int low = *max_element(weights.begin(), weights.end());
    int high = accumulate(weights.begin(), weights.end(), 0);

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int days = daysForCap(weights, mid);

        if (days <= target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low;
}