Search: Binary Search

Today we are going to explore an important class of algorithms, and the most valuable one. and that is the search algorithm. We will first discuss some theoretical concepts, and then we will look into their implementation, complexity (how costly the problem can be when the size grows), and use case.

Search:

This is something where you want to find an item or a group of items with specific properties within a much larger collection of items.

Type of Search:

Brute Force Search:- Sometimes also referred to as linear search. This is the most straightforward way to find the element. We sequentially scan all the elements in the ordered list until we find one.

def linear_search(data, target):  
   for i in range(len(data)):   
       if data[i] == target:    
           return True  
   return False

If we measure this algorithm using our complexity tool, then it's apparent that it's O(n). Why? Because we are touching every element in the worst case.

i.e O(len(data)) for the loop * O(1) to test the element. So overall complexity is O(n).

Let's assume we have a sorted list. Whether it's an integer or any other complex object, but they are sorted. We can certainly do a linear search.

# Assume list is sorted in ascending order.
def linear_sorted_search(data, target):   
   for i in range(len(data)):   
       if data[i] == target:    
           return True
       if data[i] > target:  <<-- This helps us to amortize the cost
            return False;
   return False

This is a bit better than the brute force as we have taken into consideration on below-highlighted snippet:

# Additional check to break the loop.
if data[i] > target:
    return False;

Here we leverage the fact that our list has a particular order to it. (elements are sorted in ascending order).

If we again measure this algorithm, we can see that in the worst case this will go to O(n) in terms of time complexity. Timing-wise it's a bit faster however from a complexity point of view this is still the same i.e O(n)

Can we do better?

Yes Certainly. This is where binary search comes into action.

The binary search uses the divides and conquers strategy to work in half. The idea is that divide the list into two half and search for the element.

As we have given that elements are in sorted order, we are going to pick them midway through, and check if this is the element which we are searching for? If the answer is yes then we are happy, and get the result. if the answer is no, then we have to use our IQ to find where our element could be.

As elements are sorted, and we know the mid element. Can we guess where our element could lies?

Well, yes. If the middle element we found is bigger than the target element, then we must say that our target element will lie on the left side of the middle element. If the middle element is smaller than the target element, then we conclude that our target element will lie on the right side of the middle element.

To summarise what we have discussed above:-

1. Get the middle element which divides the list in roughly half.
2. Check if this element is what we are looking for,
   2.1  If this is then we are done.
   2.2  If not, then find if this is bigger or smaller than our target number
3. Depending on 2.2 evaluation we have to throw one half the problem where solution can't exist.
4. Repeat the same approach (of starting in the middle) on the new half-size problem.

Make sense? Yes!!! Carry on.

Now we have just converted our bigger problem (Problem of finding the target element in the bigger list) in half. This process continues until we get the target element. We can easily see that the nature of the problem is recursive. isn’t it?

Here is the recursive version of the code:-

def binary_search(data, target, low, high):
    if low == high:
        return data[mid] == target
    else:
        mid = (low + high) // 2 <-- integer divide
        if target == data[mid]:
            return True
        elif target < data[mid]:
            return binary_search_recursive(data, target, low, mid-1) <-- thrown away the half of the list
        else:
            return binary_search_recursive(data, target, mid+1, high) <-- thrown away the half of the list

Let's find the time complexity:

In each step, we divide our problem in half until we reached that particular target element. if n is the number of items in the list, then our equation will be something like this:

n * (1/2) * (1/2) * (1/2)*… = 1 <<- 1 becuase We divide the list in half until we find the target element.
n * (1/2)x = 1
This solve x to logn

So the time complexity for binary search came to O(lgn) (with base 2)

This is indeed far better than our linear search.

Bonus: Here is the iterative version of the code:

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if target == data[mid]:
            return True
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return False

Argument:

Now one can certainly argue that this is a limitation of the binary search. If we have to implement the binary search then always the list should be in sorted order.

The saying here is that it's always advisable to opt for binary search whenever the list is sorted. However, if the list is not sorted, and you have the use case of searching the element repeatedly, then you can proceed with sorting the list. This will certainly increase the time complexity, but for larger searches, this will amortize the cost.

Let's understand this math:

Sort + O(lgn) < O(n) :- Can we say this is true ?
Sort < O(n) - O(lgn)

When the above expression is true? Never Right. There is no sorting algorithm where this expression can be true.

Sort + k * O(lgn) < k * O(n)
Sort < k * (O(n) - O(lgn)) <<← This expression is going to be true for larger K.

So we have just seen a discussion on one of the important search algorithms. There are many problems that can be solved using this technique of divide and conquer search.

Happy Learning!!!