Welcome back! Today, we're adding another tool to our toolkit for algorithms and data structures — a powerful searching technique known as binary search that operates seamlessly on sorted arrays. By the end of this session, you will understand binary search, its internals, its Python implementation, and its time and space complexity.

Drawing a parallel with everyday life, binary search resembles the process of finding a word in a dictionary. Instead of skimming through every page, we open the dictionary around the middle and compare our words. If our word is in the left half, we discard the right half, and vice versa. This halving process continues until we find our word — essentially, this is a binary search.

Binary Search is a search algorithm operating on a sorted list or array. The strategy employed by Binary Search is similar to the process of searching for a name in a telephone directory or a word in the dictionary - you open the book in the middle and determine whether the name or word you're looking for can be found in the left (first half) or the right part (second half). If the name or word you're searching for is smaller than the one in the middle, you continue your search only in the left half. However, if it's larger, you narrow down your search to the right half. This method is iteratively repeated, reducing the search space by half each time, thereby making this search operation highly effective.

In Python terms, imagine you have a sorted list of numbers as: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], and you've been tasked with determining if the number 3 is present in the list. With Binary Search, it directly jumps to the middle. If the number is equal to the middle element, our search is complete. But if the number is smaller than the middle element, Binary Search discards the second half of the list and continues the search only on the first half. This process is repeated until the number is found.

Binary search uses a divide-and-conquer approach to find a specific element in a list. Regarding time complexity, this algorithm accomplishes the task in the order of $O(\log n)$, making it a preferable choice for large datasets.

The steps involved in the binary search algorithm are as follows:

1. Calculate the middle index of the list. This can be easily done by adding the lowest index and the highest index and dividing the sum by 2.
2. If the middle element is greater than the target, the target must be in the left half of the list. Discard the right partition and rerun the process on the left half.
3. If the middle element is less than the target, discard the left half of the list and continue searching the right half.
4. Repeat these steps until the length of the search interval becomes less than or equal to 1.
5. Once finished, check if data[left] equals target - if yes, we found the target element; if not - target doesn't exist in the data array.

To translate binary search into Python code, devise a function that takes in the sorted list and the target element. Start by establishing the boundaries of your search. Then, repeatedly halve the list until either the element is found or the list is exhausted. Let's implement binary search iteratively in Python:

Python
Copy to clipboard
1def binary_search_iterative(data, target):
2    # We will search in the interval [low, high), where the right border is excluded
3    low = 0
4    high = len(data)
5
6    while high - low > 1: # search until the length of the interval > 1
7        mid = (low + high) // 2
8        if target < data[mid]:
9            high = mid # Continue our search in [low, mid)
10        else:
11            low = mid # Continue our search in [mid, high)
12    return low if data[low] == target else None

In this function, the index of the target in the sorted list is returned. If the target is not found, the function returns None.

Similarly, we can implement binary search using recursion — a function that calls itself until a base case is met.

Python
Copy to clipboard
1def binary_search_recursive(data, target, low, high):
2    if high - low <= 1:
3        return low if data[low] == target else None
4    mid = (low + high) // 2
5    if target < data[mid]:
6        return binary_search_recursive(data, target, low, mid)
7    else:
8        return binary_search_recursive(data, target, mid, high)

In the recursive version, the while loop is replaced by recursive calls to the function itself. The algorithm remains the same: find the middle, compare it with the target, and determine the next step.

Binary search has excellent performance when it comes to time complexity - $O(\log n)$. This logarithmic time behavior makes binary search ideal for large datasets. This is because, with each comparison, binary search eliminates half of the elements, reducing the search time exponentially.

Regarding space complexity, the iterative version of binary search has a space complexity of $O(1)$ as it only uses a fixed amount of space to store the data. However, the recursive version has higher space complexity — $O(\log n)$ — since it uses additional space in the form of a call stack during recursive tasks.

With a clear understanding of binary search, we can now use it to solve a complex problem — searching for a target element in a rotated sorted list. This involves figuring out the rotation point and applying binary search accordingly.

Consider a list like this [7, 8, 9, 2, 3, 4]. This list was sorted from 2 to 9, but then it was rotated to the fourth position. Suppose we want to search for the number 3. We can see that it's in the latter half, but how does our algorithm determine this?

As a bonus exercise, try to apply binary search to solve this question! We will cover the analysis of this question in the next lessons.

And that's all for our binary search lesson! We've drawn parallels between binary search and looking up a word in a dictionary, explored the binary search algorithm and its Python implementation, learned how to analyze its time and space complexity, and seen how it can be used to solve more advanced problems like searching in a rotated sorted list.

Take a moment to acknowledge your accomplishment — you're now well-equipped with the knowledge of an efficient searching algorithm!

Are you eager to apply what you've just learned? Great! Up next are practice exercises based on binary search, including searching in a rotated sorted list. Solving these will expand your understanding and expose you to various practical applications of binary search. Whether you aspire to excel in your coding interview or wish to strengthen your problem-solving skills, these practice problems are your ticket to success. Let's get started!