10.1.4. Simple Recursive Algorithm for Binary Search

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, let me searches from l to r, but not including r itself.

The binary search algorithm is designed to quickly find a value in a sorted array by repeatedly dividing the search interval in half. It uses three parameters: the value to search for (K), and two indices that mark the current search boundaries (left 'l' and right 'r'). When we say the algorithm searches from index 'l' to 'r-1', it means the search considers the elements starting from 'l' up to, but not including, 'r'. This is important for avoiding out-of-bounds errors in the array while searching.

Imagine you're searching for a word in a dictionary. You don't start from the first page; instead, you might open it in the middle. If the word is earlier than the one you found, you go to the left half, otherwise you go to the right. Similarly, binary search looks for the middle value of a range and narrows down the search from there.

So, now if l and r are actually the same, then we have an empty array, because l to r minus 1 is actually something that there are no elements in the fields. So, we say we have not found it. So, when the interval that we are searching for becomes empty, the array definitely does not contain the value.

In the recursive binary search, one of the important considerations is to determine when to stop searching. If the left index 'l' equals the right index 'r', it means there are no elements to search within that range; thus, we conclude that the value 'K' is not present in the array. Recognizing this condition is crucial, as it helps prevent unnecessary computations and potential errors.

Consider looking for a book in a library. If you have already checked every shelf within a certain section and found nothing, there's no point in continuing your search in that area; it’s just empty space—a clear sign that the book isn’t there.

Otherwise, we compute the midpoint between l and r by taking the sum and dividing by 2 and because this might be an odd number, we use integer division. Now, we examine at this point we are found the midpoint. So, now, we examine if the value that we want is there at the midpoint.

After confirming that our search boundaries are valid, the next step is to locate the midpoint index of the current segment. The midpoint is calculated using the formula (l + r) / 2, making sure to use integer division to avoid fractional indices. Once we have the midpoint, we check if the value at that index equals the target value 'K'. This comparison is key to determining the next step.

Think of this step like checking a temperature at a certain height on a thermometer. The midpoint would be like looking at the halfway mark to determine if you're above or below the target temperature, helping you decide whether to adjust the temperature upwards or downwards.

If the value that we want is equal to K, we found it; otherwise, if the value that we want is smaller than the midpoint, then we go to the left and the value that we want is bigger than the midpoint, then we go to the right. So, this either goes from left to mid minus 1 or mid plus 1 to right.

Once we've checked the midpoint value, there are three possible outcomes. If the midpoint's value is equal to 'K', we successfully found our target. If the value is less than 'K', it indicates that 'K' can only be found in the right half, so we narrow our search to the section between 'mid + 1' and 'right'. Conversely, if the midpoint value is greater than 'K', we restrict our search to the left half from 'left' to 'mid - 1'. This process of continually halving the search range is what enables binary search to be efficient.

Imagine you're playing a guessing game where you have to identify a number between 1 and 100. If your guess is too low, you know the answer must be higher, so you adjust your range. If it's too high, you lower your range. This narrowing down is akin to how binary search processes its search space.

So, we can write as we saw for such recursive functions, we can write what is called a recurrence. Recurrence is just an expression for the time, in terms of smaller values with same expression.

The efficiency of binary search can be expressed using a recurrence relation that reflects the time complexity of the algorithm. Each time we search, we perform a constant time operation (the comparison) plus the time for searching in one half of the remaining elements. As a result, we can define the relationship as T(n) = T(n/2) + O(1), indicating that we are effectively halving the size of the problem with each step.

Consider a bakery that produces different types of bread. Each time they bake, they decide to either keep the batch size the same or reduce it by half depending on how successful the last batch was—this is similar to how binary search efficiently narrows down its search size.

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, when does this become 1, when n is 2 to the k in other words when k is log 2 of n. So, when I get log 2 of n, then this become T of 1 and at the next step this is going to become 1 plus T of 0. So, this is going to be log n 1s and so, over all the complexity of binary search is just order of log n.

The logarithmic time complexity of binary search is a critical advantage because it scales significantly better than linear search, especially with large datasets. Each iteration effectively eliminates half of the search space until only one element is left, indicating that the number of steps required to find 'K' relates to the logarithm (base 2) of the number of elements 'n'. Consequently, this highly efficient approach means we can search large sequences quickly.

Think of climbing to the top of a tower where each floor doubles the number of stairs. Just as each step up halves the number of remaining stairs to climb, binary search continuously reduces its search space, making it much faster than having to climb every single stair.

--