Binary Search

Binary Search is the question that quietly shows up everywhere. So many harder problems hide a binary search inside them. Get this one clean and a whole family of questions becomes easy. The interviewer wants to see if you can search a sorted list without checking every single item.

🎯 The Problem

You get a sorted array and a target, and you must find where the target sits. Here are the rules.

• The array is sorted from small to big.
• You get one target number.
• Return the position of the target in the array.
• If the target is not there, return -1.
• Every number is different.

A sorted array means every number is in order, so you can make smart guesses instead of checking one by one. In [-1, 0, 3, 5, 9, 12] the target 9 sits at position 4, so the answer is 4.

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4

Explanation: nums[4] = 9, so the position is 4

Here is the array laid out with its positions. We are hunting for 9.

🐢 Approach 1: Linear Scan (Brute Force)

The idea in one line: check every number from left to right until you find the target.

The idea:

• Walk the array from the first item to the last.
• If an item equals the target, return its position.
• If you reach the end with no match, return -1.

How it works:

• This is a linear scan. You look at every item, one after another.
• It always works, even on an unsorted array.

Why it is weak:

• The array is already sorted, but the scan ignores that.
• For a big array you might check almost every number.
• That is O(n) time, since the worst case touches all n items.

Here is the linear-scan code for that idea:

def search(nums, target):
    for i, num in enumerate(nums):
        if num == target:
            return i
    return -1

⚡ Approach 2: Binary Search (Best)

The idea in one line: jump to the middle and throw away half the array each step.

The idea:

• Keep three markers. lo is the left edge, hi is the right edge, mid is between them.
• Look at the number at mid and compare it with the target.

How it works:

• If the middle number equals the target, you are done.
• If the middle is smaller than the target, the target is to the right. Move lo to just past mid.
• If the middle is bigger than the target, the target is to the left. Move hi to just before mid.

Why it is fast:

• Each step throws away half of what is left.
• A list of a million numbers takes only about twenty steps.
• That is O(log n) time. The “log” is how many times you can halve the list before one item is left.

Here is a dry run searching for 9. Watch how lo, mid and hi close in.

Steps to Solve

1. Set lo to 0 and hi to the last position of the array.
2. While lo is less than or equal to hi, keep searching.
3. Find the middle position mid as lo + (hi - lo) / 2.
4. If the number at mid equals the target, return mid.
5. If the number at mid is smaller than the target, move lo to mid + 1.
6. If the number at mid is bigger than the target, move hi to mid - 1.
7. If the loop ends without a match, return -1.

#include <stdio.h>

int binarySearch(int nums[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // middle, avoids overflow
        if (nums[mid] == target) {
            return mid;                // found it
        } else if (nums[mid] < target) {
            lo = mid + 1;              // target is to the right
        } else {
            hi = mid - 1;              // target is to the left
        }
    }
    return -1;                          // not found
}

int main(void) {
    int nums[] = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    printf("%d\n", binarySearch(nums, 6, target));
    return 0;
}

4

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int lo = 0, hi = (int)nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // middle position
        if (nums[mid] == target) {
            return mid;                // found it
        } else if (nums[mid] < target) {
            lo = mid + 1;              // go right
        } else {
            hi = mid - 1;              // go left
        }
    }
    return -1;                          // not found
}

int main() {
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    cout << binarySearch(nums, target) << endl;
    return 0;
}

4

public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;  // middle position
            if (nums[mid] == target) {
                return mid;                // found it
            } else if (nums[mid] < target) {
                lo = mid + 1;              // go right
            } else {
                hi = mid - 1;              // go left
            }
        }
        return -1;                          // not found
    }

    public static void main(String[] args) {
        int[] nums = { -1, 0, 3, 5, 9, 12 };
        int target = 9;
        System.out.println(binarySearch(nums, target));
    }
}

4

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2     # middle position
        if nums[mid] == target:
            return mid                # found it
        elif nums[mid] < target:
            lo = mid + 1              # target is to the right
        else:
            hi = mid - 1              # target is to the left
    return -1                          # not found


nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(binary_search(nums, target))

4

function binarySearch(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2); // middle position
    if (nums[mid] === target) {
      return mid;        // found it
    } else if (nums[mid] < target) {
      lo = mid + 1;      // go right
    } else {
      hi = mid - 1;      // go left
    }
  }
  return -1;             // not found
}

const nums = [-1, 0, 3, 5, 9, 12];
const target = 9;
console.log(binarySearch(nums, target));

4

Let us walk through the Python version line by line, so you see why each line is there.

The line lo, hi = 0, len(nums) - 1 sets the two edges of the search. lo starts at the very first position. hi starts at the very last position. Together they mark the part of the array we still care about.

The line while lo <= hi: keeps the search going as long as there is at least one item left to check. The moment lo passes hi, the window is empty and we stop.

The line mid = lo + (hi - lo) // 2 picks the middle position. We write it this way, not as (lo + hi) // 2, because in other languages adding two big numbers can overflow. This form is safe and means the same thing.

The line if nums[mid] == target: checks the middle number. If it is the target, we return mid right away. That is the happy ending.

The line elif nums[mid] < target: handles a middle number that is too small. The target must be in the right half. So we set lo = mid + 1 and throw the whole left half away.

The else branch handles a middle number that is too big. The target must be in the left half. So we set hi = mid - 1 and drop the right half.

If the loop finishes with no match, return -1 tells the caller the target is simply not there.

⏱️ Time and Space Complexity

The linear scan checks one item at a time, so it can touch every item. That makes it O(n). Binary search cuts the list in half every step, so it finishes in about log n steps. Neither one needs extra memory beyond a few variables, so the space is O(1) for both.

🧩 Key Takeaways

• ✅ Binary search only works when the array is already sorted.
• ✅ Keep three markers: lo for the left edge, hi for the right edge, mid in between.
• ✅ Each step throws away half of what is left, so it runs in O(log n) time.
• ✅ Use lo + (hi - lo) / 2 for the middle to stay safe from overflow.
• ✅ Return -1 when the loop ends with no match.

🚀 What’s Next?

• Find Minimum in Rotated Sorted Array
• Koko Eating Bananas