Binary Search
Binary search is a highly efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. At each step, it compares the target to the middle element and discards the half in which the target cannot lie. With a time complexity of O(log n), binary search is dramatically faster than linear search for large sorted datasets.
Key Formula
mid = floor((low + high) / 2)
LaTeX: mid = \left\lfloor \frac{low + high}{2} \right\rfloor
| Symbol | Meaning | Unit |
|---|---|---|
| mid | Index of the middle element | index |
| low | Lower bound index of the current search range | index |
| high | Upper bound index of the current search range | index |
Worked Example
Problem
Search for the value 37 in the sorted array [2, 5, 8, 12, 16, 23, 37, 45, 56, 72].
Solution
Step 1: low=0, high=9, mid=4 → array[4]=16. 37 > 16, so search right half. Step 2: low=5, high=9, mid=7 → array[7]=45. 37 < 45, so search left half. Step 3: low=5, high=6, mid=5 → array[5]=23. 37 > 23, so search right half. Step 4: low=6, high=6, mid=6 → array[6]=37. Target found!
Answer
Value 37 found at index 6 in 4 steps (vs. 7 steps for linear search).
Binary Search vs Linear Search Comparison
| Property | Binary Search | Linear Search |
|---|---|---|
| Time Complexity | O(log n) | O(n) |
| Space Complexity | O(1) iterative | O(1) |
| Prerequisite | Array must be sorted | No requirement |
| Steps for n=1,000,000 | ~20 | ~500,000 (avg) |
| Best Case | O(1) | O(1) |
| Worst Case | O(log n) | O(n) |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Big O Notation
Big O notation is a mathematical notation used to describe the upper bound of an algorithm's growth rate in terms of time or space, characterising its worst-case performance as the input size approaches infinity. It abstracts away constant factors and lower-order terms, focusing on the dominant factor that determines scalability. Big O is the industry standard language for comparing algorithm efficiency and is essential for technical interviews and software engineering.
Algorithm
An algorithm is a finite, ordered sequence of well-defined instructions or rules designed to solve a specific problem or accomplish a task. Algorithms are fundamental to computer science because they provide a systematic approach to computation, independent of any particular programming language or hardware. They are evaluated on correctness, efficiency, and clarity, and form the basis of every software program ever written.
Merge Sort
Merge sort is an efficient, stable, divide-and-conquer sorting algorithm that works by recursively splitting an array into two halves, sorting each half, and then merging the sorted halves back together. It guarantees a time complexity of O(n log n) in all cases — best, average, and worst — making it more predictable than quicksort. Merge sort is the preferred algorithm for sorting linked lists and is used in many standard library implementations such as Python's Timsort.
The concept of binary search derives from the mathematical principle of bisection, known since antiquity. The first formal description of binary search for sorted lists was given by John Mauchly in 1946. The algorithm was first published by D.H. Lehmer in 1960.