Binary Search
Binary search is an efficient algorithm for finding a target value within a sorted list or array. It works by repeatedly dividing the search interval in half. If the middle element is the target, the search is successful. If the target is smaller than the middle element, the search continues in the left half. If the target is larger, the search continues in the right half. This process repeats until the target is found or the interval is empty (meaning the target is not in the list).
Suppose you have a sorted array [2, 5, 7, 8, 11, 12] and you want to find the number 13. Binary search would first look at the middle element, 8. Since 13 is greater than 8, it would discard the left half and consider [11, 12]. The new middle element is 11. Since 13 is greater than 11, it considers [12]. Now the middle element is 12. Since 13 is greater than 12, it considers the right half, which is empty. Therefore, 13 is not found and the algorithm terminates.Binary search operates on the principle of divide and conquer. Its time complexity is O(log n), where n is the number of elements in the list. This logarithmic complexity makes it significantly faster than linear search (O(n)) for large datasets. Binary search requires the data to be sorted beforehand. The algorithm can be implemented iteratively or recursively, both achieving the same logarithmic time complexity.