Binary Search From Basics

Binary Search is one of the most fundamental and powerful algorithmic techniques every developer should know.

It appears everywhere: coding interviews, databases, operating systems, and performance-critical applications.
And once you truly understand it, you'll start seeing it hidden inside many other problems.

What You'll Learn in This Guide

• How binary search actually works

• The thought process behind it

• Common real-world variations

What Is Binary Search?

Binary Search is a way to quickly find an element inside a sorted array.
Instead of checking each element one by one (which is slow), it keeps cutting the data structure in half each time.

Method	Operations (approx.)	Example (1M elements)
Linear Search	O(n)	1,000,000 checks
Binary Search	O(log n)	~20 checks

That's an incredible performance boost.

Binary Search Requirements

To use binary search effectively, make sure your data:

1. Is sorted (in ascending or descending order)

2. Supports random access (like arrays or lists, not linked lists)

The Binary Search Mindset

Almost all binary search problems follow the same mental pattern:

1. Define the search space => left, right

2. Find the middle element => mid = (left + right) / 2

3. Decide which half to eliminate

4. Repeat until the condition fails

Once you internalize this pattern, you can adapt it to solve dozens of problems, not just searching for a number.

1. Classic Binary Search : Find the Target's Index

Problem: Given a sorted array, find the index of the target element.
If not found, return -1.

Thinking Process:

• We repeatedly check the middle element.

• If it's equal => we're done.

• If it's larger => search the left half.

• If it's smaller => search the right half.

Code

    public int Search(int[] nums, int target) {
       int left = 0, right = nums.Length - 1;

       while (left <= right) {
           int mid = left + (right - left) / 2;

           if (nums[mid] == target)
               return mid;
           else if (target < nums[mid])
               right = mid - 1;
           else
               left = mid + 1;
       }

       return -1;
    }

2. Search Insert Position: Where Should It Go?

Problem: If the target isn't found, return the index where it should be inserted to keep the array sorted.

Thinking Process:

Throughout the algorithm:

• left = the first index that could possibly contain the target

• right = the last index that could possibly contain the target

On every iteration, we shrink the search space:

• If nums[mid] is less than target => we move left to mid + 1

• If nums[mid] is greater than target => we move right to mid - 1

Eventually, left passes right, meaning: The target must lie between right and left.

If the target exists, the function will have already returned its index before the loop ends.

Otherwise, left becomes the position of the next greater element, which is exactly the correct insertion point.

Code

public int SearchInsert(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

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

            if (nums[mid] > target)
                right = mid - 1;
            else
                left = mid + 1;
        }

        return left; // insertion point
    }

3. Find the Smallest Letter Greater Than Target

Problem: Given a sorted list of letters, find the smallest letter greater than a target.
If none exist, wrap around and return the first letter.

Thinking Process

• We're looking for the first element greater than the target.

• If we reach the end => wrap around to index 0.

Code

    public char NextGreatestLetter(char[] letters, char target) {
        int left = 0, right = letters.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (letters[mid] <= target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return left == letters.Length ? letters[0] : letters[left];
    }

Binary search can find the first element that satisfies a condition, not just equality.

4. Count Negative Numbers in a Sorted Matrix

Problem: Each row in the matrix is sorted in non-decreasing order.
Count the total number of negative numbers.

Thinking Process

• Each row is sorted => binary search can find the first negative element.

• Once we know the first negative index, we can compute how many negatives follow.

Code

    public int CountNegatives(int[][] grid) {
        int cols = grid[0].Length;
        int count = 0;

        foreach (var row in grid) {
            int left = 0, right = cols - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (row[mid] < 0)
                    right = mid - 1;
                else
                    left = mid + 1;
            }

            count += cols - left;
        }

        return count;
    }

If you're learning C# and algorithms, binary search is one of the best skills to master early.

Once you get comfortable with its logic, problems that seemed hard suddenly start looking easy.