Binary search

Your interviewer at Microsoft slides a whiteboard marker across the table and says, "Find a number in a sorted array." If your first instinct is to loop through every element, you've already lost points. Binary search, also known simply as Binary Search on platforms like LeetCode, is one of the most fundamental algorithms in computer science. It's the reason you can look up a word in a dictionary without reading every page, and it's a pattern that shows up in far more interview problems than you might expect.

TL;DR

Maintain two pointers, lo and hi, bounding the search space. Compute the middle index, compare the middle element to the target, and eliminate half the array each iteration. If the middle element matches, return true. If the target is larger, search right (lo = mid + 1). If smaller, search left (hi = mid - 1). Stop when lo > hi. This runs in O(log n) time and O(1) space.

Why This Problem Matters

Binary search is the gateway to an entire family of interview problems. Once you internalize the pattern of halving a search space, you'll recognize it in rotated array searches, finding insertion points, searching for first/last occurrences, and even abstract problems where you binary search on the answer itself. Microsoft, Google, and Amazon all test variations of this pattern regularly.

Understanding the Problem

We're given a sorted array of integers and a target value. We need to return true if the target exists in the array, false otherwise.

binarySearch([2, 5, 9], 9)  -> true
binarySearch([2], 4)         -> false

The key constraint is that the array is sorted in ascending order. This ordering is what makes binary search possible.

Edge Cases

1. Empty array: No elements to search, return false
2. Single element: Either matches or doesn't
3. Target at boundaries: First or last element
4. Target not in array: Search space collapses without a match

Solution Approach

Think about looking up a word in a physical dictionary. You don't start at page one and flip through every page. You open the book roughly in the middle, check if you've gone too far or not far enough, then repeat with the correct half. That's binary search.

For the array [2, 5, 8, 9, 10, 12], searching for 9:

Three comparisons and we've found our target. A linear scan would have taken four. The difference grows massively with larger arrays: for a million elements, binary search needs at most 20 comparisons versus a million for linear scan.

Now searching for 7 (not in the array):

The search space collapses when lo exceeds hi, and we know the element isn't present.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public Boolean binarySearch(int[] arr, int n) {
    int lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
      int mid = (lo + hi) / 2;

      if (arr[mid] < n) {
        lo = mid + 1;
      } else if (arr[mid] > n) {
        hi = mid - 1;
      } else {
        return true;
      }
    }

    return false;
  }
}

Breaking this down:

1. Initialize boundaries: lo starts at 0, hi at the last index
2. Loop while the search space is valid: lo <= hi means there's still at least one element to check
3. Calculate the midpoint: (lo + hi) / 2 gives us the middle index
4. Three-way comparison: The middle element is either less than, greater than, or equal to our target
5. Narrow the search: Move lo right or hi left to eliminate half the array
6. Return false if not found: The loop ends when the search space is empty

Why lo <= hi and not lo < hi?

Consider searching for 5 in [5]. Initially lo = 0, hi = 0. With lo < hi, the loop never executes and we'd incorrectly return false. The <= ensures we check the last remaining element.

The Integer Overflow Subtlety

In production code, (lo + hi) / 2 can overflow if both values are large. The safer formula is lo + (hi - lo) / 2. For interview arrays this rarely matters, but mentioning it shows awareness of real-world concerns.

Complexity Analysis

Time: O(log n) where n is the array length. Each iteration cuts the search space in half. The maximum number of iterations is the number of times you can divide n by 2 before reaching 1, which is log2(n). For a billion-element array, that's roughly 30 comparisons.

Space: O(1). We use three integer variables (lo, hi, mid) regardless of the input size.

Binary Search vs. Linear Search

The logarithmic growth of binary search is what makes it so powerful. The array size can grow by orders of magnitude while the search cost barely increases.

Common Pitfalls

1. Using lo < hi instead of lo <= hi: Misses the case where the target is the single remaining element. Always use <=.

2. Setting lo = mid instead of lo = mid + 1: When arr[mid] < n, we know mid isn't the answer. Setting lo = mid keeps it in the search space and can cause an infinite loop when lo == hi.

3. Off-by-one on hi: When arr[mid] > n, set hi = mid - 1, not hi = mid. Same reasoning: mid is already eliminated.

4. Forgetting the empty array: arr.length - 1 is -1 for empty arrays. The lo <= hi condition handles this naturally since 0 <= -1 evaluates to false, but it's worth verifying.

Interview Tips

When presenting binary search:

• Start by confirming the array is sorted. If it's not sorted, binary search doesn't apply.
• Write the loop condition lo <= hi and explain why <= is correct.
• Mention the overflow-safe midpoint formula as a bonus.
• If asked for a follow-up, discuss variants: finding the insertion point, first/last occurrence, or searching a rotated array.
• Binary search is a building block. Show that you see it as a pattern, not just a single algorithm.

Key Takeaways

• Binary search achieves O(log n) time by eliminating half the search space with each comparison, using only O(1) space.
• The loop condition must be lo <= hi (not lo < hi) to correctly handle single-element search spaces.
• Always update lo = mid + 1 and hi = mid - 1 (not lo = mid or hi = mid) to avoid infinite loops and ensure progress.
• The pattern extends far beyond simple element lookup: rotated arrays, insertion points, first/last occurrence, and answer-space binary search all build on this foundation.
• For very large arrays, use mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2 to avoid integer overflow.

Practice and Related Problems

Once you're comfortable with basic binary search, try these progressions:

• Insertion index finder (binary search for the correct position)
• Search in a rotated sorted array
• Find first and last occurrence of a value
• Find the minimum in a rotated sorted array

This problem and hundreds of others are available on Firecode, where spaced repetition helps you internalize patterns like binary search so they become second nature during interviews. Whether you're prepping for Microsoft, Google, or your first tech job, building strong fundamentals here pays off in every round.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def binary_search(self, arr: List[int], n: int) -> bool:
        lo = 0
        hi = len(arr) - 1

        while lo <= hi:
            mid = (lo + hi) // 2

            if arr[mid] < n:
                lo = mid + 1
            elif arr[mid] > n:
                hi = mid - 1
            else:
                return True

        return False

JavaScript

class Solution {
  binarySearch(arr, n) {
    let lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
      let mid = Math.floor((lo + hi) / 2);

      if (arr[mid] < n) {
        lo = mid + 1;
      } else if (arr[mid] > n) {
        hi = mid - 1;
      } else {
        return true;
      }
    }

    return false;
  }
}

TypeScript

class Solution {
  binarySearch(arr: number[], n: number): boolean {
    let lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
      const mid = Math.floor((lo + hi) / 2);

      if (arr[mid] < n) {
        lo = mid + 1;
      } else if (arr[mid] > n) {
        hi = mid - 1;
      } else {
        return true;
      }
    }

    return false;
  }
}

C++

#include <vector>

class Solution {
public:
  bool binarySearch(std::vector<int> arr, int n) {
    int lo = 0, hi = arr.size() - 1;

    while (lo <= hi) {
      int mid = (lo + hi) / 2;

      if (arr[mid] < n) {
        lo = mid + 1;
      } else if (arr[mid] > n) {
        hi = mid - 1;
      } else {
        return true;
      }
    }

    return false;
  }
};

Go

package solution

func (s *Solution) BinarySearch(slice []int, n int) bool {
    lo, hi := 0, len(slice)-1

    for lo <= hi {
        mid := (lo + hi) / 2

        if slice[mid] < n {
            lo = mid + 1
        } else if slice[mid] > n {
            hi = mid - 1
        } else {
            return true
        }
    }

    return false
}

Scala

class Solution {
  def binarySearch(arr: Array[Int], n: Int): Boolean = {
    var lo = 0
    var hi = arr.length - 1

    while (lo <= hi) {
      val mid = (lo + hi) / 2

      if (arr(mid) < n) {
        lo = mid + 1
      } else if (arr(mid) > n) {
        hi = mid - 1
      } else {
        return true
      }
    }

    false
  }
}

Kotlin

class Solution {
    fun binarySearch(arr: IntArray, n: Int): Boolean {
        var lo = 0
        var hi = arr.size - 1

        while (lo <= hi) {
            val mid = (lo + hi) / 2

            if (arr[mid] < n) {
                lo = mid + 1
            } else if (arr[mid] > n) {
                hi = mid - 1
            } else {
                return true
            }
        }

        return false
    }
}

Swift

class Solution {
    func binarySearch(_ arr: [Int], _ n: Int) -> Bool {
        var lo = 0
        var hi = arr.count - 1

        while lo <= hi {
            let mid = (lo + hi) / 2

            if arr[mid] < n {
                lo = mid + 1
            } else if arr[mid] > n {
                hi = mid - 1
            } else {
                return true
            }
        }

        return false
    }
}

Rust

impl Solution {
    pub fn binary_search(&self, arr: Vec<i32>, n: i32) -> bool {
        let mut lo: i32 = 0;
        let mut hi: i32 = arr.len() as i32 - 1;

        while lo <= hi {
            let mid = (lo + hi) / 2;

            if arr[mid as usize] < n {
                lo = mid + 1;
            } else if arr[mid as usize] > n {
                hi = mid - 1;
            } else {
                return true;
            }
        }

        false
    }
}

C#

public class Solution {
    public bool binarySearch(int[] arr, int n) {
        int lo = 0, hi = arr.Length - 1;

        while (lo <= hi) {
            int mid = (lo + hi) / 2;

            if (arr[mid] < n) {
                lo = mid + 1;
            } else if (arr[mid] > n) {
                hi = mid - 1;
            } else {
                return true;
            }
        }

        return false;
    }
}

Dart

class Solution {
  bool binarySearch(List<int> arr, int n) {
    int lo = 0, hi = arr.length - 1;

    while (lo <= hi) {
      int mid = (lo + hi) ~/ 2;

      if (arr[mid] < n) {
        lo = mid + 1;
      } else if (arr[mid] > n) {
        hi = mid - 1;
      } else {
        return true;
      }
    }

    return false;
  }
}

PHP

class Solution {
    public function binarySearch(array $arr, int $n): bool {
        $lo = 0;
        $hi = count($arr) - 1;

        while ($lo <= $hi) {
            $mid = intdiv($lo + $hi, 2);

            if ($arr[$mid] < $n) {
                $lo = $mid + 1;
            } elseif ($arr[$mid] > $n) {
                $hi = $mid - 1;
            } else {
                return true;
            }
        }

        return false;
    }
}

Ruby

class Solution
  def binary_search(arr, n)
    lo, hi = 0, arr.length - 1

    while lo <= hi
      mid = (lo + hi) / 2

      if arr[mid] < n
        lo = mid + 1
      elsif arr[mid] > n
        hi = mid - 1
      else
        return true
      end
    end

    false
  end
end