3.7.2.2 Binary Search
Algorithms and Problem Solving
Binary Search is an efficient algorithm for finding an item in a sorted list. It works by repeatedly dividing the search interval in half and discarding the half where the item cannot be, until the item is found or the interval is empty.
Process:
- Start with the middle element of the sorted list.
- If the middle element is the target, return its position.
- If the target is smaller than the middle element, repeat the search on the left half.
- If the target is larger, repeat the search on the right half.
Example: Suppose you have a sorted list [1,3,5,7,9,11,13] and you are searching for the number
- Binary Search will start at the middle element (7) and find the target immediately.
Complexity: The time complexity of Binary Search is O(log n), making it much faster than linear search algorithms, especially for large datasets. Figure 3.7 illustrates the binary search process, showing how the search interval is halved at each step, making the search more efficient.