Binary Search

Overview

Binary search is an efficient algorithm for finding an element in a sorted array. It repeatedly divides the search space in half by comparing the target value with the middle element, eliminating half of the remaining elements with each comparison.

The Divide and Conquer Approach

Binary search compares the target with the middle element of the current search range. If they match, the search is complete. If the target is smaller, it searches the left half. If larger, it searches the right half. This continues until found or the range becomes empty.

Why It Requires Sorted Data

Binary search relies on the array being sorted. This ordering allows the algorithm to eliminate half the elements based on a single comparison. Without sorted data, you cannot determine which half to search next.

Time Complexity

Binary search has O(log n) time complexity in all cases. Each comparison eliminates half the remaining elements, so even for large arrays, very few comparisons are needed. This makes it extremely efficient compared to linear search for sorted data.

The Search Process

The algorithm maintains left and right pointers defining the current search range. It calculates the middle index, compares that element with the target, and adjusts the pointers accordingly. When left exceeds right, the target is not in the array.

Applications

Beyond searching, binary search principles are used in finding insertion points, determining ranges, and solving optimization problems where you need to find a value satisfying certain conditions. It's one of the most important algorithms in computer science.

When to Use Binary Search

Use binary search whenever you have sorted data and need to find an element efficiently. The O(log n) performance makes it ideal for large datasets. If data isn't sorted, consider sorting first if you'll perform many searches, or use linear search for occasional queries.