Binary search is one of the most fundamental algorithms in computer science. It efficiently finds a target value in a sorted array by repeatedly dividing the search space in half. This approach gives us a time complexity of O(log n), making it much faster than linear search for large datasets.
The binary search algorithm follows a systematic approach. We start with pointers at both ends of the array and find the middle element. We compare the target with the middle element and decide which half to search next. This process continues until we find the target or exhaust the search space.
Let's trace through an example of finding the number 11. In the first step, we compare 11 with the middle element 9 at index 4. Since 11 is greater than 9, we discard the left half and focus on the right half. This demonstrates how binary search eliminates half of the remaining elements in each step.
Here's the implementation of binary search in Python. The algorithm uses two pointers, left and right, to track the current search boundaries. In each iteration, we calculate the middle index and compare the middle element with our target. Based on the comparison, we adjust our search boundaries. The time complexity is O(log n) because we halve the search space in each step, and the space complexity is O(1) for the iterative version.
Binary search has numerous real-world applications including database indexing, search engines, and game development. Its main advantage is the logarithmic time complexity, making it extremely efficient for large datasets. For example, in an array of 1000 elements, linear search might take up to 1000 steps, while binary search needs at most 10 steps. However, binary search requires the data to be sorted, which is its main limitation.