10.1.5. Time Complexity of Binary Search

So, on the other hand if the sequence is sorted and in particular if it is an array, we can be a little more intelligent. So, what we know is that the values are assigned in ascending order. So, if you probe the value in the middle and check is this equal to K, if the value that we have is equal to K of course, we have found it. If it is smaller than the value here, then we only need to search this half, and if it is larger than we need to search in this half.

When we have a sorted array, we can apply a more efficient search method known as binary search. Instead of checking each element one-by-one, binary search allows us to eliminate half of the elements at each step. By checking the middle element of the array:

1. If it's equal to our target value K, we've found our answer.
2. If it's smaller than K, we know that K must be in the upper half of the array.
3. If it's larger than K, K must be in the lower half. This method dramatically reduces the number of checks needed compared to linear search.

Think about searching for a word in a dictionary. You don’t go through each word one-by-one; instead, you open the dictionary roughly in the middle and see if your word is on that page. If it’s earlier in the alphabet, you go to the earlier half of the dictionary, and if it’s later, you go to the later half. This way, you find the word much faster!

So, here is a simple recursive algorithm for binary search. So, in general it searches an array, remember that when we do the search we might be searching different segments depending on how far we progress the search. So, in general binary search takes a value K to search an array and two end points, left and right and just to make sure that we get a everything right, you will have the convention that it searches from the index l to the index r minus 1.

The binary search algorithm can be implemented recursively. The function takes three parameters: the target value K, and the left and right bounds of the current search segment, l and r. It operates as follows:

1. First, it checks if the current segment is valid (l < r). If it's not, the value isn't found.
2. It then calculates the midpoint index.
3. If the midpoint value equals K, it returns success.
4. If K is less than the midpoint value, the search continues in the left segment (from l to mid-1).
5. If K is greater than the midpoint value, it continues in the right segment (from mid+1 to r). This process repeats until K is found or the segment is invalid.

Consider how you might organize a treasure hunt in a large field. Instead of searching every inch of the field, you divide it into quarters. You check one quarter first. If the treasure isn’t there, you can eliminate that quarter from your search and focus only on the remaining three quarters. You continue dividing until you find the treasure or confirm it's not in the field.

So, the crucial advantage of binary search is that each step we have the interval to search and at some point we will reach 1 and then when we have 1, we will get an interval of size 0 and so, we will get an immediate answer. So, we can write as we saw for such recursive functions, we can write what is called a recurrence. The base case is that when we have T of n we mean the time taken to search in a list or an array actually of size n. So, T of 0 is 1.

Binary search is highly efficient, with its time complexity being logarithmic, O(log n). This means that the number of operations needed to find K grows much slower than the size of the array. Specifically, every time we check the midpoint, we effectively halve the search space. Using recurrence relations, we define T(n) as the time taken to search in an array of size n, and we find that:

• T(0) = 1, which means if there are no elements, we can conclude immediately.
• For any other n, the recurrence T(n) = 1 + T(n/2) represents the time taken for each comparison plus the time for the next half. This logarithmic growth leads us to a very efficient search time even for large datasets.

Imagine you’re searching for your friend in a crowded mall. If you were to look through every person (linear search), it would take a long time. But what if you asked each section of the mall if they’ve seen your friend? After checking a few larger groups, you may quickly narrow down to just one section where your friend is. Binary search acts similarly, consistently narrowing the search area, allowing you to find your friend much faster.

So, we mentioned in the previous unit about arrays and list that, things that work on list may not work on arrays and vice versa. So, here is an example of something it works only for arrays. The idea of looking up the midpoint and then going left works only, if you can find the midpoint constant time, if you have to spend time looking for the constant for the midpoint, then you cannot get this recurrence anymore which not going to be 1 plus T of n by 2, but it is going to be n plus T of n by 2 plus here n by 2 and then we will actually get a linear.

It's crucial to note that binary search can only be efficiently applied to data structures that allow for constant time access, like arrays. If, for instance, you were using a linked list where you had to traverse elements to find the midpoint, the efficiency drops dramatically. In this case, finding the midpoint during each call would take linear time, rendering the binary search less efficient, as it would not maintain the original logarithmic complexity.

Think of a bookshelf where books are stacked behind each other in a random order (like in a linked list). If you want to find the book in the middle, you can’t just ‘jump’ to it without removing the books in front. This is like losing the efficiency of binary search because you have to check more before you can determine where to look next.

--