Intro to Python for Computer Science and Data Science: Learning to Program with AI, Big Data and The Cloud

11.9 Binary Search

The binary search algorithm is more efficient than linear search, but it requires a sorted array. The first iteration of this algorithm tests the middle element in the array. If this matches the search key, the algorithm ends. Assuming the array is sorted in ascending order, then if the search key is less than the middle element, it cannot match any element in the second half of the array and the algorithm continues with only the first half of the array (i.e., the first element up to, but not including, the middle element). If the search key is greater than the middle element, it cannot match any element in the first half of the array and the algorithm continues with only the second half (i.e., the element after the middle ...