Binary Search

Say you have a list of a million sorted numbers. You need to find one of them. Checking each number one by one is slow. You might look at almost the whole list before you find it. Binary search fixes that pain. It throws away half the list on every single check. So a million numbers takes only about twenty looks.

📖 What Is Binary Search?

Binary search is a way to find a value in a sorted array fast. Sorted means the values are already in order. They go from smallest to largest.

The idea is simple. You look at the middle value first. Then you ask one question. Is my target smaller or bigger than this middle?

• If the target is smaller, it must be on the left side. So you ignore the right half.
• If the target is bigger, it must be on the right side. So you ignore the left half.
• If the middle is exactly your target, you are done.

Every check cuts the remaining numbers in half. That is why it is so fast.

📚 A Real-World Analogy

Think about finding a word in a paper dictionary. You don’t start at page one and read every word. That would take forever.

Instead you open the dictionary somewhere in the middle. Say you are looking for “mango”. You land on a page with “rabbit”. Now “mango” comes before “rabbit”. So you flip to the left half. You open the middle of that half and land on “garden”. This time “mango” comes after “garden”. So you jump to the right. You keep splitting like this until you land on the page with “mango”.

That is binary search. A dictionary only works this way because the words are in order. The same rule applies here. The array must be sorted first. If it is not, binary search gives wrong answers.

🔍 How It Works

We keep two markers. One is low. It marks the start of the part we are still searching. The other is high. It marks the end of that part. At the start, low is the first index and high is the last index.

Then we repeat these moves. We stop when we find the target or run out of range.

• Find the middle index: mid = (low + high) / 2.
• Look at arr[mid].
• If arr[mid] equals the target, return mid. We found it.
• If the target is smaller than arr[mid], the answer is on the left. Set high = mid - 1.
• If the target is bigger than arr[mid], the answer is on the right. Set low = mid + 1.

When does it stop? It stops when low becomes greater than high. That means the range is empty and the target is not there. So we return -1.

Here is the whole flow as a picture.

Let’s trace a quick example. Say the array is [2, 5, 8, 12, 16, 23, 38, 56] and we want 23.

Two checks and we found it. A linear scan would have taken six.

📝 Steps to Do Binary Search

Before we write code, let’s list the steps in order.

1. Set low to 0 and high to the last index of the array.
2. Repeat while low is less than or equal to high.
3. Calculate mid as low + (high - low) / 2.
4. If arr[mid] equals the target, return mid.
5. If the target is greater than arr[mid], set low = mid + 1.
6. If the target is smaller than arr[mid], set high = mid - 1.
7. If the loop ends without a match, return -1.

💻 Binary Search in Code

Now let’s write binarySearch(arr, target). It returns the index where the target sits. If the target is not in the array, it returns -1. The array is already sorted.

#include <stdio.h>

// Returns the index of target in a sorted array, or -1 if not found
int binarySearch(int arr[], int n, int target) {
    int low = 0;
    int high = n - 1;

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

        if (arr[mid] == target) {
            return mid;                    // found it
        } else if (target > arr[mid]) {
            low = mid + 1;                 // go right
        } else {
            high = mid - 1;                // go left
        }
    }
    return -1;                             // not found
}

int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 56};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Index of 23: %d\n", binarySearch(arr, n, 23));
    printf("Index of 5: %d\n", binarySearch(arr, n, 5));
    printf("Index of 100: %d\n", binarySearch(arr, n, 100));
    return 0;
}

Index of 23: 5
Index of 5: 1
Index of 100: -1

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

// Returns the index of target in a sorted array, or -1 if not found
int binarySearch(const vector<int>& arr, int target) {
    int low = 0;
    int high = (int)arr.size() - 1;        // cast to int for a safe range

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

        if (arr[mid] == target) {
            return mid;                    // found it
        } else if (target > arr[mid]) {
            low = mid + 1;                 // go right
        } else {
            high = mid - 1;                // go left
        }
    }
    return -1;                             // not found
}

int main() {
    vector<int> arr = {2, 5, 8, 12, 16, 23, 38, 56};

    cout << "Index of 23: " << binarySearch(arr, 23) << endl;
    cout << "Index of 5: " << binarySearch(arr, 5) << endl;
    cout << "Index of 100: " << binarySearch(arr, 100) << endl;
    return 0;
}

Index of 23: 5
Index of 5: 1
Index of 100: -1

public class BinarySearch {

    // Returns the index of target in a sorted array, or -1 if not found
    static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

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

            if (arr[mid] == target) {
                return mid;                    // found it
            } else if (target > arr[mid]) {
                low = mid + 1;                 // go right
            } else {
                high = mid - 1;                // go left
            }
        }
        return -1;                             // not found
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 8, 12, 16, 23, 38, 56};

        System.out.println("Index of 23: " + binarySearch(arr, 23));
        System.out.println("Index of 5: " + binarySearch(arr, 5));
        System.out.println("Index of 100: " + binarySearch(arr, 100));
    }
}

Index of 23: 5
Index of 5: 1
Index of 100: -1

def binary_search(arr, target):
    """Return the index of target in a sorted list, or -1 if not found."""
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + (high - low) // 2   # safe middle

        if arr[mid] == target:
            return mid                  # found it
        elif target > arr[mid]:
            low = mid + 1               # go right
        else:
            high = mid - 1              # go left

    return -1                           # not found


arr = [2, 5, 8, 12, 16, 23, 38, 56]

print("Index of 23:", binary_search(arr, 23))
print("Index of 5:", binary_search(arr, 5))
print("Index of 100:", binary_search(arr, 100))

Index of 23: 5
Index of 5: 1
Index of 100: -1

// Returns the index of target in a sorted array, or -1 if not found
function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2); // safe middle

    if (arr[mid] === target) {
      return mid;            // found it
    } else if (target > arr[mid]) {
      low = mid + 1;         // go right
    } else {
      high = mid - 1;        // go left
    }
  }
  return -1;                 // not found
}

const arr = [2, 5, 8, 12, 16, 23, 38, 56];

console.log("Index of 23:", binarySearch(arr, 23));
console.log("Index of 5:", binarySearch(arr, 5));
console.log("Index of 100:", binarySearch(arr, 100));

Index of 23: 5
Index of 5: 1
Index of 100: -1

⏱️ Complexity Summary

Here is how binary search compares. This shows you why it shines on big sorted arrays.

To feel the difference, think about a million items. Linear search can take a million checks. Binary search takes about twenty. That is the gift of halving.

⚠️ Common Mistakes

A few things trip people up the first time.

• Running binary search on an array that is not sorted. The left-or-right choice only makes sense in order. So you get wrong answers.
• Writing low < high instead of low <= high. With the wrong sign you can skip the last element. Then you miss a target that is really there.
• Forgetting to move low or high. If you don’t shrink the range, the loop never ends.
• Using (low + high) / 2 on very large arrays. The sum can overflow. Use low + (high - low) / 2 to stay safe.

🧩 What You’ve Learned

✅ Binary search finds a value in a sorted array. It checks the middle and cuts the range in half each time.

✅ You keep two markers, low and high. You move them based on whether the target is smaller or bigger than the middle.

✅ It runs in O(log n) time and O(1) space. So it stays fast even on huge arrays.

✅ The array must be sorted first, or the result is wrong. Use linear search if the data is not in order.

✅ Use low + (high - low) / 2 for the middle. This avoids overflow on large arrays.

🚀 What’s Next?

• Linear Search
• Binary Search: Iterative vs Recursive
• Search in Rotated Sorted Array