# Binary Search: No Memorizing, No Crying - 1

Let me guess how your binary search journey went.

You watched a video. The algorithm made perfect sense. You nodded confidently, like someone who has understood everything. Then you opened your first problem and the solution had `low < high`. The next one had `low <= high`. Then `high` started at `nums.size()` instead of `nums.size() - 1`, and suddenly `high = mid` appeared, as if nobody had told you the rules had changed.

Your brain did what every brain does when it feels lost: it started memorizing. *"Okay, first occurrence uses this one, lower bound uses that one..."*

Yeah. I did that too. I got completely overwhelmed. And I'll save you the suspense: **memorizing templates works right up until the problem wears a slightly different shirt.** Then you're back to staring at the screen like it owes you money.

So here's the deal. In this series you won't memorize a single template. You'll understand *why* each variation exists, and then you'll be able to rebuild any of them from scratch, even at 2 AM with a deadline and no WiFi.

Binary search comes down to five patterns:

![A road with five signposts, two completed and three still hidden in mist](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/f97fe3db-d0f5-410c-960f-d3ce8192b254.png align="center")

1. Element Search (Exact Match)
2. Boundary Search (First/Last Occurrence)
3. Modified Binary Search (Rotated / Partially Sorted Arrays)
4. Peak Finding / Bitonic Array Search
5. Search in Answer Space

This post covers the first two. The rest get their own posts. Grab a notebook (a real one, your phone doesn't count), and let's go.

## Nobody searches their contacts from the top

![Two panels comparing scrolling a contact list from the top with jumping through it in halves](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/5f22c2dc-22b4-4458-b8d6-101e30f27450.png align="center")

Say you want to call your friend Zoya. Do you start at the first contact and scroll one by one: *Aaditya... Aarav... Abhishek...*?

Of course not. You jump to the middle, see "M", and think *"Z comes after M"*, so you jump into the second half. Then you land on "T", jump again, and you're on Zoya in a few moves.

Congratulations, you already do binary search in real life. You just never got a certificate for it.

Linear search is the person who scrolls from "A" every single time. We all know one of them, and we don't trust them with directions either.

## So what is binary search, officially?

Given a **sorted** array and a target, look at the **middle** element:

- If it equals the target, done.
- If it's smaller than the target, the target must be on the right, so ignore the left half completely.
- If it's bigger, the target must be on the left, so ignore the right half.

Repeat until you find it or run out of elements. If the search space becomes empty, the target isn't there, and we return `-1`.

How good is that? For 1,000,000 elements, linear search might do up to 1,000,000 checks. Binary search does about **20**. Twenty. Linear search is still on the first page while binary search has already made chai and is back.

## The only idea you really need: the invariant

Here comes the one thing I want you to remember even if you forget everything else:

> **If the target exists, it is always inside** `[low, high]`**.**

This is called an **invariant**: a promise the algorithm keeps on every single iteration. And unlike your friend's *"bro I'm just 5 minutes away"*, this promise is never broken.

Every line of the code exists to keep that promise true. When `arr[mid] < target`, then `mid` and everything left of it can't be the answer, so we throw them out with `low = mid + 1`. The target is still inside `[low, high]`. Promise kept.

Now notice a small thing about `high = mid - 1`. It means `high` is a **real candidate**, a position that might still hold the answer. So `[low, high]` is a *closed interval*: both ends are alive. Keep this in your head, because it explains the loop condition in a minute, and it's the secret to why the other versions look different later.

## "Sorted array required" is only half the story

Everyone says binary search needs a sorted array. True, but boring, and slightly wrong.

The real rule:

> **You must be able to look at one thing and safely throw away half the search space.**

Sorted order is just the easiest way to get that guarantee. Later in the series you'll see problems with no sorted array at all, where a simple yes/no condition gives the same power. That's Binary Search on Answer, and when it clicks you'll feel like you've been handed a cheat code.

## The code

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

Barely ten lines. Type it yourself. I know your Ctrl+C is faster than your brain, but today we're fixing that.

Two tiny details that stop real bugs:

- `mid = low + (high - low) / 2` instead of `(low + high) / 2`. If both are huge, adding them can overflow the integer range. This version never does. Fun fact: this exact overflow bug sat in Java's standard library for years before it was caught. If it can fool the people who wrote Java, it can fool you at 1 AM.
- `(int)arr.size() - 1` instead of `arr.size() - 1`. `size()` is unsigned, so on an empty vector `size() - 1` doesn't give `-1`. It wraps around to a gigantic number. Storing it straight into an `int` happens to turn it back into `-1` on most compilers, so you can get away with it. But change `high` to `size_t`, or compare it against another unsigned value, and the loop runs wild and reads memory that isn't yours. The cast says "I want a signed number here" out loud, and that's a habit worth having.

## Watch it work: target found

```plaintext
Array:  [1, 3, 5, 7, 9, 11, 13]
Target: 9
```

![Playful Binary Search Infographic](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/05fadcd0-1724-4084-9ee8-e2b138d6f323.png align="center")

| Iteration | low | high | mid | arr\[mid\] | What happens |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | 6 | 3 | 7 | 7 &lt; 9, so target is on the right: `low = 4` |
| 2 | 4 | 6 | 5 | 11 | 11 > 9, so target is on the left: `high = 4` |
| 3 | 4 | 4 | 4 | 9 | Found it at index 4 |

Look at iteration 3 again. `low` and `high` are **equal**, and there's still one element left to check. Put a pin in that. It's about to matter.

## Watch it work: target NOT found

Same array, but now we hunt for `6`, which does not exist. No amount of staring will make it appear. (Yes, like when you keep opening the fridge hoping something new showed up.)

![Binary Search_ Target 6 Not Found](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/aed496fe-2a68-4d9e-91ab-d76bf5ff4405.png align="center")

| Iteration | low | high | mid | arr\[mid\] | What happens |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | 6 | 3 | 7 | 7 > 6, so `high = 2` |
| 2 | 0 | 2 | 1 | 3 | 3 &lt; 6, so `low = 2` |
| 3 | 2 | 2 | 2 | 5 | 5 &lt; 6, so `low = 3` |

Now `low = 3` and `high = 2`. The pointers have **crossed**: nothing is left to check. The loop ends and we return `-1`. That's how binary search knows the target isn't there. It doesn't give up. It simply runs out of places to look.

**Quick pause.** Try this before scrolling: what does the code return for an empty array `[]`? Think for ten seconds. Don't scroll down yet. I can see you. Backbenchers always peek at the answers first.

*(Answer:* `high` *becomes* `-1`*, so* `low <= high` *is* `0 <= -1`*, which is false. The loop never runs and we return* `-1`*. If you got it right, nice. If not, that's exactly why we're here.)*

## The great `low <= high` vs `low < high` mystery

If you've ever changed `<` to `<=` and prayed, this section is your intervention.

This one confused me the most, and the invariant solves it in seconds.

Take `arr = {10, 20, 30}` and `target = 30`. After one step we're at `low = 2, high = 2`. One element left, and it's the one we want.

If the condition is `low < high`, the loop looks at equal pointers, decides *"we're done here"* and leaves, without ever checking that last element. We return `-1`, and the answer was standing right there.

With `low <= high`, the loop continues, because `[2, 2]` is a closed interval with a live candidate in it. This is the idea from earlier: `high` is inclusive, so equal pointers still mean there's something left to check.

So the `<=` was never random. It came straight from how we defined the interval. (Remember this, because I'm about to use it against you. Lovingly. And if you forget, you owe me a chai.)

## How fast is it, really?

Each iteration halves the search space. So the real question is: **how many times can you halve** `n` **before only one element is left?** About log₂(n).

| Array size | Linear Search (worst) | Binary Search (worst) |
| --- | --- | --- |
| 1,000 | 1,000 checks | ~10 iterations |
| 1,000,000 | 1,000,000 checks | ~20 iterations |
| 1,000,000,000 | 1,000,000,000 checks | ~30 iterations |

A **billion** elements in about 30 steps. Your phone takes longer to load a reel.

**Time complexity: O(log n).** We drop the base of the log because logs of different bases differ only by a constant factor, and Big-O doesn't care about constants. (Big-O is a bit like me: big-hearted enough to ignore the spare change you borrowed from me.)

**Space complexity: O(1)** for the iterative version. We only use `low`, `high`, and `mid`. A recursive version uses O(log n) for the call stack.

## Okay, you're feeling confident. Good. Now the truth bomb.

![A proud student celebrates while a friend sneaks up holding a cartoon bomb](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/32d8c388-0737-435f-8cf0-0f0dc4171f86.png align="center")

At this point you understand binary search. You can explain it, dry-run it, even defend `<=` in an argument. Be proud, you earned it.

Now go solve a real problem and watch me ruin your day.

Our code finds *an* index where the target lives. **Not necessarily the first one.**

Try `[1, 2, 2, 2, 3]` with target `2`. The first `mid` is index 2, it matches, and we happily return 2. But the *first* occurrence is index 1. We never even looked there.

Think of your contacts again. You have three people saved as "Rahul": *Rahul College*, *Rahul Gym*, and *Rahul Don't Pick Up*. If you want the first Rahul, stopping at the first one you stumble on isn't good enough. You need a different way of thinking about the search.

![Three contacts all named Rahul, with the first one highlighted](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/abc57b66-12f1-4a1e-a74a-e714375b3e3d.png align="center")

And here's the other truth bomb: binary search is famous for being easy to explain and hard to write correctly. People who've been coding for years still slip on those boundary conditions. So if you're making bugs here, you aren't bad at this. You're exactly on schedule.

---

## Boundary Search

Until now we used binary search for **exact match**: find the target, then stop.

Boundary search asks a different question: **where does something begin or end?** Where's the first `2`? The last `2`? The first element that's greater than or equal to some value?

Broadly, boundary search comes in two flavours: **lower bound** and **upper bound**. To understand them, I'm dragging you back to school.

### The backbencher's guide to boundaries

Let's be honest: you were a backbencher. Don't deny it. Your last-page doodles are the evidence. So this one's for you.

It's assembly time, and 7 students are already lined up by height, because school has never heard of freedom:

```plaintext
Index:   0    1    2    3    4    5    6
Height: 150  155  160  160  160  165  170
```

You're 160 cm, and (shocker) you're late. You need to slip into the line without breaking the height order. Your life goal hasn't changed since class: **stay as far from the teacher as possible.**

**Scenario 1: The teacher is at the end of the line.** You want maximum distance, so you go to the *earliest* spot that keeps the order: right in front of the first 160 cm student, **index 2**.

![A late student sneaks into a school line before the PT teacher notices / strolls in behind classmates of his own height.](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/7e636cae-f7e2-4631-9e43-ae20bd9b3f84.png align="center")

**Scenario 2: The teacher is at the front of the line.** Same goal, opposite direction. You go to the *latest* legal spot, right behind the last 160 cm student: **index 5**.

![A late student sneaks into a school line](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/0a237ec9-27bc-4832-ae04-33867feabbb1.png align="center")

Standing anywhere from index 2 to 5 keeps the line sorted, so you have four legal spots. But you're a backbencher, so you'll always pick an edge. Boundary search finds those **two edges**. That's all it does.

- **Lower bound:** the smallest index where the element is **greater than or equal to** the target. (Scenario 1, index 2)
- **Upper bound:** the smallest index where the element is **strictly greater than** the target. (Scenario 2, index 5)

If every element is smaller than the target, both bounds return `n`, the length of the array: the spot right behind the last student. (Upper bound also returns `n` when everyone is smaller than *or equal to* the target, since nobody is strictly taller.)

### Seeing it on an array

`arr = [1, 2, 2, 2, 4, 5, 8]`

![Screenshot 2026-11-13 200624](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/08f981ec-0862-404b-9c39-e77b49e67973.png align="center")

| Target | In the array? | Lower bound | Upper bound |
| --- | --- | --- | --- |
| 2 | Yes | 1 (the first 2) | 4 (the value 4, first element > 2) |
| 3 | No | 4 (the value 4, first element ≥ 3) | 4 (the value 4, first element > 3) |

Two things worth noticing:

- When the target is **absent**, both bounds are equal. The zone has zero width: there's nowhere to stand *among* equals, because there are no equals.
- When the target is **present**, `upper bound - lower bound` is the number of occurrences. Here, 4 - 1 = 3 twos.

Remember the three Rahuls in your contacts? The first Rahul is the lower bound. The last Rahul is the upper bound minus 1. How many Rahuls you have is upper bound minus lower bound. Duplicates problem, solved.

### The one picture behind boundary search

Before any code, here's the trick that makes all of this click. Pick a yes/no question, ask it about every element, and write the answers in a row.

**Lower bound's question:** *"Is this element ≥ target?"* With `target = 2`:

![Lower Bound](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/4cd0d25d-348a-4828-8b44-10758b643d42.jpg align="center")

```plaintext
Index:    0  1  2  3  4  5  6
Value:    1  2  2  2  4  5  8
>= 2 ?    F  T  T  T  T  T  T
             ^ lower bound = 1
```

**Upper bound's question:** *"Is this element > target?"* Same target:

![Upper Bound](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/5213f84a-de7d-471e-96fa-7152912cfc17.jpg align="center")

```plaintext
Index:    0  1  2  3  4  5  6
Value:    1  2  2  2  4  5  8
> 2 ?     F  F  F  F  T  T  T
                   ^ upper bound = 4
```

Because the array is sorted, the row always looks like `F F F ... T T T`. It never goes `T` then back to `F`. And once you see that, boundary search is just one job: **find the first** `T`**.** Lower bound and upper bound are the same algorithm asking different questions. (If every answer is `F`, there's no `T` to point at, so the answer is `n`, the spot behind the last element.)

This is also why binary search works here at all. Look at *one* element: if it says `F`, everything to its left is `F` too, so throw the left side away. If it says `T`, everything to its right is `T` too, so throw the right side away (but keep this one, it might be the *first* `T`). That's the same "throw away half" rule from earlier, and it's the exact idea that will power Binary Search on Answer later in the series, where there's no array at all, just a yes/no question.

### Lower bound, line by line

```cpp
int lowerBound(const vector<int>& arr, int target) {
    int low = 0, high = (int)arr.size();
    int ans = (int)arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target) {
            ans = mid;
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}
```

Here `ans` is our **best answer so far**. Look at the middle element and ask the `T`/`F` question: **is** `arr[mid] >= target`**?**

- `T`**:** `mid` is a possible answer, so we note it down: `ans = mid`. But an earlier index might qualify too. So we *can't* return yet, and we can't throw `mid` away either, because it might be the earliest one. We keep `mid` and discard everything to its right: `high = mid`.
- `F`**:** `mid` is too short, and so is everything to its left. None of them can be the answer, so `low = mid + 1`.

Why does `ans` start at `n`? Because if no element ever passes the test, nobody in the line is tall enough, and the answer is the spot right behind the last student: index `n`.

Notice something different from exact search: there's no "found it!" moment. We keep shrinking until `low` and `high` meet, and `ans` holds the last answer that passed the test. (Fun detail: when the loop ends, `ans`, `low` and `high` are all the same number. We keep `ans` because it says out loud what we're tracking.)

Let's dry-run `target = 2` on `[1, 2, 2, 2, 4, 5, 8]`:

| Iteration | low | high | mid | arr\[mid\] | What happens | ans |
| --- | --- | --- | --- | --- | --- | --- |
| Start | 0 | 7 |  |  |  | 7 |
| 1 | 0 | 7 | 3 | 2 | 2 >= 2, so `ans = 3`, `high = 3` | 3 |
| 2 | 0 | 3 | 1 | 2 | 2 >= 2, so `ans = 1`, `high = 1` | 1 |
| 3 | 0 | 1 | 0 | 1 | 1 &lt; 2, so `low = 1` | 1 |

Now `low == high == 1`. The loop stops and we return `ans`, which is **1**, the first 2.

Look at iteration 1. `mid` landed on a 2 at index 3 and exact search would have returned right there. Lower bound shrugs and keeps going, because it wants the *first* one.

**One gotcha:** lower bound returns a *position*, not a yes/no. For `target = 3` it returned 4, the spot where 3 *would* go. To check whether the target is really present, test `idx < n && arr[idx] == target`.

**Pause and try:** what does `lowerBound` return for `target = 9` and `target = 0` on this array? No peeking. Yes, you, in the last row. *(Answers: 7 and 0. Nothing is ≥ 9, so we get* `n`*. Everything is ≥ 0, so we get the very first spot.)*

Now you're probably wondering about `low < high`, `high = arr.size()` and `high = mid`. Just be calm and hold your veins. We'll crack all three right after upper bound, because seeing the two side by side is when it finally clicks.

### Upper bound, line by line

```cpp
int upperBound(const vector<int>& arr, int target) {
    int low = 0, high = (int)arr.size();
    int ans = (int)arr.size();
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] > target) {
            ans = mid;
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return ans;
}
```

Spot the difference from lower bound? Go on, I'll wait.

It's **one character**: `>=` became `>`. Same loop, same updates, same `ans`, and you've just built a completely different concept.

The question we ask is now: **is** `arr[mid] > target`**?**

- `T`**:** `mid` is strictly taller than you, so it's a possible answer: `ans = mid`. An earlier index might qualify too, so we keep `mid` and discard everything to its right: `high = mid`.
- `F`**:** `mid` is *not taller* than you (it's shorter or the same height). It isn't an answer and neither is anything to its left, so `low = mid + 1`.

That second bullet is the whole trick. Students exactly your height count as "not taller", so you walk right past them and stand behind the last one. Classic backbencher move: Scenario 2.

Let's dry-run `target = 2` on `[1, 2, 2, 2, 4, 5, 8]`:

| Iteration | low | high | mid | arr\[mid\] | What happens | ans |
| --- | --- | --- | --- | --- | --- | --- |
| Start | 0 | 7 |  |  |  | 7 |
| 1 | 0 | 7 | 3 | 2 | 2 is not > 2, so `low = 4` | 7 |
| 2 | 4 | 7 | 5 | 5 | 5 > 2, so `ans = 5`, `high = 5` | 5 |
| 3 | 4 | 5 | 4 | 4 | 4 > 2, so `ans = 4`, `high = 4` | 4 |

Now `low == high == 4`. The loop stops and we return `ans`, which is **4**, the first element strictly greater than 2.

Compare iteration 1 with lower bound's iteration 1. Same `mid`, same value 2, but lower bound went *left* and upper bound went *right*. Equal elements are the only place the two disagree, and that's the entire difference between them.

## The mystery, solved

Remember I told you to hold your veins? You held them. Good. Time to pay off the promise.

All three weird things (`high = arr.size()`, `low < high`, `high = mid`) come from one change of meaning:

> In exact search, `[low, high]` holds **positions to inspect**. In boundary search, `[low, high]` holds **possible answers**.

And in terms of the `F F F T T T` row from earlier, the promise looks like this: **everything left of** `low` **is** `F`**, everything from** `high` **onward is** `T`**, and the first** `T` **is trapped somewhere in between.** Every update keeps that promise true.

And that second one is a bigger set than you'd think. Let's see why.

### 1\. Why `high = arr.size()`

In exact search, `low` and `high` are positions we might *look at*, so every value had to be a valid index. That's why `high` started at `n - 1`.

In boundary search we're not hunting for an element. We're hunting for a **position to return**, and there's one more legal answer than there are elements: `n`, the spot behind the last student. It's what you get when nobody qualifies. So the possible answers are `0` through `n`, and `high` has to start at `n`.

"But won't that read `arr[n]` and crash?" Nope. `high` is never read as an element, it's only a *candidate answer*. And inside the loop we have `low < high`, so `mid` is always strictly less than `high`, which means `mid` never goes past `n - 1`.

### 2\. Why `low < high`

Two reasons, and the second one is a classic bug.

**Reason 1: when** `low == high`**, the work is done.** Our interval holds possible *answers*, not elements. If `low` and `high` meet, exactly one possible answer is left, and that's *the* answer. There's nothing left to check. (In exact search, equal pointers still left one element to inspect. That's why that version needed `<=`. Remember that? Or am I gonna get a chai?)

**Reason 2:** `<=` **would break things.** Take `arr = [2, 3, 5, 7, 11]` and `target = 15`:

- `low = 0, high = 5`: `mid = 2`, 5 &lt; 15, so `low = 3`
- `low = 3, high = 5`: `mid = 4`, 11 &lt; 15, so `low = 5`
- Now `low == high == 5`

With `low <= high`, the loop would run once more, compute `mid = 5`, and read `arr[5]`, which doesn't exist. In C++ that's undefined behaviour, not a friendly error message.

And if you ever wrote `<=` together with `high = mid`, you'd also get the classic **infinite loop**: once `low == high` and `mid` passes the test, `high = mid` changes nothing, and the loop spins forever. If your code hung and you blamed the judge's server, this was probably it.

### 3\. Why `high = mid` and not `mid - 1`

In exact search, whenever we moved a pointer, `mid` had just been **rejected**: it wasn't the target, so throwing it away was safe (`mid + 1` or `mid - 1`).

In boundary search, we move `high` when `mid` **passes** the test. It's a valid answer, maybe even *the* answer. Throwing it away with `mid - 1` could throw away the very spot we're looking for. So we keep it: `high = mid`.

The rule to remember isn't a rule at all, just common sense:

> **If** `mid` **fails, discard it. If** `mid` **passes, keep it.**

### The whole thing in one table

|  | Exact search | Boundary search |
| --- | --- | --- |
| What is `[low, high]`? | Positions to inspect | Possible answers (`0` to `n`) |
| `high` starts at | `n - 1` | `n` |
| Loop runs while | `low <= high` | `low < high` |
| `mid` fails | Discard it (`mid ± 1`) | `low = mid + 1` |
| `mid` passes | Return it | Note it and keep it: `ans = mid`, `high = mid` |

Notice that you didn't have to memorize any of this. Every row follows from the first one. Change what `[low, high]` means, and everything else changes with it. That's exactly what I promised you at the start.

---

## Plot Twist: Boundary Search Can Use `<=` Too

![Midnight Coding Loop](https://cdn.hashnode.com/uploads/covers/6af568de663c1a81315582ff/3531ee21-3515-47c1-b3cb-167b4978f2fd.png align="center")

Right after learning all this, I felt unstoppable. Confident, high on dopamine, solving boundary problems one after another.

Then I hit one I couldn't crack, so I peeked at the solution. And there it was, in a *boundary search* problem: `low <= high`.

The famous GTA meme hit me: *"Oh sh\*t ,here we go again*." I was back where I started.

Then it clicked. The solution wasn't wrong and neither was mine. It was a **different style of the same algorithm**, and I had only learned one of them.

### The other style

If you use `low <= high`, then `[low, high]` goes back to meaning *positions still to inspect*, so exactly three things change, and they change **together**:

1. `high` starts at `n - 1` instead of `n`
2. the loop becomes `low <= high` instead of `low < high`
3. `high = mid - 1` replaces `high = mid`

Here's lower bound in this style:

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

|  | The `low < high` style | The `low <= high` style |
| --- | --- | --- |
| `high` starts at | `n` | `n - 1` |
| Loop runs while | `low < high` | `low <= high` |
| `mid` passes | `ans = mid`, `high = mid` | `high = mid - 1` |
| `mid` fails | `low = mid + 1` | `low = mid + 1` |
| Returns | `ans` (or `low`, same value) | `low` |

Two things to notice:

- **The three changes travel as a package.** Take `low <= high` but keep `high = mid`, and you're back to the infinite loop from earlier. Take `high = n` with `low <= high`, and you read `arr[n]`. Pick a style and keep all of it.
- `ans` **is optional.** When the loop ends, `low` is sitting on the answer, so `return low` works in both styles. In the `low <= high` code above I dropped `ans` entirely. A passing `mid` gets discarded by `high = mid - 1`, but `low` keeps creeping up until it lands right on it. In the earlier `low < high` code I kept `ans` because it says out loud what we're tracking.

### So what's the real lesson?

Not "memorize both styles". It's the opposite. If you understand what `[low, high]` *means*, you can write whichever style you like and know it's right, because the rest follows from that one decision.

By convention, a lot of people use the `low < high` style for boundary search. So that's the style I'll use in this series, and you only have to hold one in your head.

## Practice problems

Try them yourself first. I'll know if you peek. (I won't. But your conscience will, and it sits in the front row.)

Ordered from easy to hard:

1. **Binary Search** (LeetCode 704): the plain exact-match template from the first half of this post. Warm-up.
2. **Search Insert Position** (LeetCode 35): "where would this go?" is lower bound wearing a disguise.
3. **Find Smallest Letter Greater Than Target** (LeetCode 744): upper bound, but with letters. Read what happens when nothing is greater.
4. **Count Occurrences in a Sorted Array** (GeeksforGeeks): remember the Rahul counter? Upper bound minus lower bound.
5. **Find First and Last Position of Element in Sorted Array** (LeetCode 34): both bounds in one problem, plus the "is it even there?" check from the gotcha above.

*Next up: Binary Search on rotated and partially sorted arrays, where the array is "sorted-ish" and your confidence will be tested again. See you there.*