DSA sheet · Binary Search · Classic binary search pattern

Binary Search Basics

This is the first question of the classic binary search pattern: LeetCode 704, "Binary Search". Find a target in a sorted array and return its index, or −1. The teacher first shows the obvious linear search, then explains, with an everyday example from school, why a sorted array lets us do much better. Then she builds binary search step by step: why we look at the middle, why we move to mid + 1 / mid - 1, why we check "equal" first, and why the loop is while left <= right.

Why it matters: every later binary search problem is this loop with small changes. If these four decisions are clear, the rest of the sheet is much easier.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Linear search (the simple way)
• Part B · Binary search (the optimal way)
• Part C · Revision page

Part 0 · Before starting

Words we will use

• Index: the position of an item. Python starts at 0, so an array of n items has indexes 0 … n−1. The last index is n - 1.
• Sorted in ascending order: each item is bigger than (or equal to) the one before it.
• Search range: the part of the array where the target could still be. We mark its two ends with left and right (also called low and high).
• mid: the index in the middle of left and right.

Why binary search works here

Because the array is sorted, one comparison at mid tells us which side can't contain the target. If nums[mid] is smaller than the target, everything left of mid is even smaller, so we can drop all of it. If it's bigger, everything right of mid is even bigger, so we drop that. Each comparison throws away half.

The mid formula

In this video the teacher writes mid = (left + right) / 2, because the constraints are small (n ≤ 10⁴). The safer form she uses from the next video on is mid = left + (right - left) // 2. They give the same index. The second one never adds two big numbers, so in Java/C++ it can't go past the int limit (2³¹ − 1) and wrap to a negative number (overflow). Python ints never overflow, so both are safe in Python. We use the safe form anyway, as a habit.

Part A · Linear search (the simple way)

LeetCode 704

1The question in simple words

You get an array nums of integers, sorted in ascending order, and an integer target. If the target is in the array, return its index. If not, return −1 (which means "not found").

target = 9 → answer 4. target = 2 → answer −1.

2What the constraints tell us

• 1 ≤ nums.length ≤ 10⁴. The array is never empty. Roughly 10⁸ simple operations is where TLE (Time Limit Exceeded) starts. 10⁴ is far below that, so even a full scan is fine. But O(n²) here would be 10⁸, right at the edge, so don't do anything quadratic.
• All values are unique and the array is sorted. Sorted is the big hint for binary search.
• Values are between −10⁴ and 10⁴: small, a normal int is fine.

3Intuition

The teacher says there are two kinds of searching: linear and binary. Linear is the obvious one: start at index 0 and look at every item one by one until you find the target or reach the end. Since all we have to do is find one value, this is a valid answer.

4Building the logic

• At each index i: if nums[i] == target, we found it → return i.
• If we finish the loop without finding it → return −1.

5Approach steps

1. For i from 0 to n−1: if nums[i] == target, return i.
2. After the loop, return −1.

6Code (Python)

class SolutionLinear:
    def search(self, nums, target):
        for i in range(len(nums)):
            if nums[i] == target:
                return i        # found it
        return -1               # checked everything, not there

7Code line by line

8Dry run

target 9 in [-1, 0, 3, 5, 9, 12]: check −1 ✗, 0 ✗, 3 ✗, 5 ✗, 9 ✓ → return 4. That's 5 looks. For target 20, we'd check all 6 and return −1.

9Complexity & remember

• Time O(n), space O(1).

Part B · Binary search (the optimal way)

1The question

Same question. Now we use the sorted order to bring the time down from O(n) to O(log n).

2What the constraints tell us

Same as Part A. n ≤ 10⁴, so linear would pass too, but binary search is what the problem is testing. The values and indexes are small, so left + right can't overflow even in Java. That's why the teacher uses the simple (left + right) / 2 in this video. We still write the safe form.

3Intuition: we already do this in daily life

The teacher's example: in school, for the morning assembly, students stand in a line sorted by height. If a teacher is looking for a student she knows is short, she doesn't start from the tall end of the line. She goes straight to the short end. Without calling it that, she's using the sorted order to skip most of the line. That's the spirit of binary search.

Now in an array. Suppose we're looking for 9, and we happen to land on 3.

• 3 is smaller than what we want.
• The array is sorted, so everything to the left of 3 is smaller still. None of it can be 9.
• So we ignore the left side and search only the right side.

The rule: pick a point, compare it with the target, and drop the side that can't contain it. Smaller than the target → drop the left, go right. Bigger → drop the right, go left.

4Building the conditions from examples

Which point do we pick? Always the middle

We can't pick at random. A random pick might be near one end and drop only a tiny piece. So by definition we always compare with the middle of the current range. Whatever the comparison says, half the range goes away.

First decide the range: from index 0 (left) to index n − 1 (right). In our array that's 0 to 5 (length 6). Middle = (0 + 5) / 2 = 2.5 → 2 (we drop the decimal). nums[2] = 3.

mid is smaller than the target → left = mid + 1

3 < 9, so 9 must be on the right. We move the left pointer forward. To where? To mid + 1, not mid.

mid equals the target → return mid (check this first)

The new range is 3 … 5. Middle = 4, nums[4] = 9. Here we don't need "less than" or "greater than". We just check whether they're equal. They are, so there's nothing left to search: return index 4.

That's why, in the code, the equal check comes before the less-than check: if we've found it, we stop right away.

mid is bigger than the target → right = mid - 1

Suppose instead mid had landed on 12 while we search for 9. Everything from 12 onward is too big, so the answer must be to the left. Move the right pointer back. To mid or mid − 1?

When does the loop stop? while left <= right

The left pointer only moves right, and the right pointer only moves left. So at some point they meet, and then cross. Once they've crossed, the range is empty and there's nothing more to search. So we keep looping only while left <= right.

The target is missing → return −1 after the loop

The teacher's example: search for 20 in the same array.

• mid = 2 (3): 20 is bigger → left = 3.
• Range 3 … 5, mid = 4 (9): still bigger → left = 5.
• Now left and right are both at index 5. mid = 5 (12): still bigger → left = 6.
• left (6) has passed right (5). They crossed, the loop ends. We never found 20 → return −1.

If the target is found, the return inside the loop ends the function, and the final return -1 never runs. If that last line does run, it means we never found the target.

5Approach steps

1. left = 0, right = len(nums) - 1.
2. While left <= right: mid = left + (right - left) // 2.
3. If nums[mid] == target → return mid.
4. Else if nums[mid] < target → left = mid + 1 (go right).
5. Else → right = mid - 1 (go left).
6. After the loop → return −1.

6Code (Python)

class Solution:
    def search(self, nums, target):
        left = 0
        right = len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid              # found
            elif nums[mid] < target:
                left = mid + 1          # target is on the right
            else:
                right = mid - 1         # target is on the left
        return -1                       # pointers crossed: not present

7Code line by line

8Dry run

Found: target 9

Not found, bigger than everything: target 20

Not found, in the middle: target 2

9Complexity & remember

Every comparison sends us either left or right, so half of the range is ignored. After 1 step n/2 items are left, after 2 steps n/4, then n/8, and so on, until 1 is left. The number of steps k satisfies n / 2^k = 1, so k = log₂ n.

• Time O(log n), space O(1).

The teacher ends with a reminder: binary search isn't only about finding an index in an array. Coming next in the sheet: rotated arrays, lower bound, binary search on the answer, and binary search on a 2D matrix.

Part C · Revision page

s = Solution()
print(s.search([-1, 0, 3, 5, 9, 12], 9))    # 4
print(s.search([-1, 0, 3, 5, 9, 12], 20))   # -1
print(s.search([-1, 0, 3, 5, 9, 12], 2))    # -1
print(s.search([5], 5))                     # 0
print(SolutionLinear().search([-1, 0, 3, 5, 9, 12], 9))   # 4

Based on this video: Binary Search | Classic Binary Search pattern