Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Python

Introduction to Divide and Conquer With Binary Search

This lesson introduces the divide and conquer technique of solving a problem using binary search in a sorted list.

We'll cover the following...

Divide and conquer is an algorithmic paradigm in which the problem is repeatedly divided into subproblems until we reach a point where each problem is similar and atomic, i.e., can’t be further divided. At this point, we start solving these atomic problems and combining (merging) the solutions. So, divide and conquer solutions have the following three steps:

  1. Divide
  2. Conquer
  3. Merge

Let’s take an example to grasp this concept better.

Binary search method

Consider a sorted list lst, of n integers. We are required to find if a particular integer value exists in the given list or not.

%0 node_1 2 node_2 4 node_3 7 node_1551329432742 8 node_1551329492659 10 node_1551329543950 13 node_1551329479805 14 node_1551329567033 17 node_1551329474396 31 node_1551329514663 94 node_1551332277696 99
A sorted list of 11 integers

Now, we could go about searching the list in a linear manner, starting from the 0th index, checking the value at each index as we move towards the 10th index. But a fascinating property of sorted lists is that, regardless of the element we are looking at, we can be sure that the next element will either have a value greater than or equal to the current element. Similarly, the previous element will either have a value lesser than or equal to the current element.

In sorted lists, the value at index i+1 is greater than or equal and the value at index i-1 is lesser than or equal to the element at index i.

How can we use this property? If we are looking for a key k in the array at any particular index i, there are three possibilities:

  1. lst[i] == k, in which case we have found the key
  2. lst[i] < k, in which case the key must exist in the right sublist (considering the list is sorted in an ascending order)
  3. lst[i] > k, in which case the key must exist in the left sublist (considering the list is sorted in an ascending order)

Visualization

The following illustration gives a quick visualization of the pseudo-code above:

Code

The following code illustrates the divide and conquer approach while using binary search:

Python 3.5
# Below is a binary search function implemented recursively
# If the required element, x, is in the given list, lst, its location will be returned
# Otherwise, if the element is not in the list, -1 will be returned
def binary_search(lst, left, right, key):
    """
    Finds a key in the list
    :param lst: List of integers
    :param left: Left sided index of the list
    :param right: Right sided index of the list
    :param key: An integer to find in the list
    :return: The index of the key in the list if found, -1 otherwise
    """
    if right >= left:
        mid_element = left + (right - left) // 2
        # If the required element is found at the middle index
        if lst[mid_element] == key:
            return mid_element
        # If the required element is smaller than the element at the middle index
        # It can only be present in the left sub-list
        if lst[mid_element] > key:
            return binary_search(lst, left, mid_element - 1, key)
        # Otherwise, it would be present in the right sub-list
        return binary_search(lst, mid_element + 1, right, key)
    # If the element is not in the list
    return -1
# Driver code to test above function
if __name__ == '__main__':
    lst = [2, 4, 7, 25, 60]
    key = 25  # to find, feel free to change this
    result = binary_search(lst, 0, len(lst) - 1, key)
    if result == -1:
        print("Element is not present in the list")
    else:
        print("Element is present at index: ", result)

Explanation

Here, binary search is implemented recursively. If the required key is found in the given list lst, the index is returned. Else, if the key is not found, −1 is returned anyway.

As explained in the visualization above, the code follows this procedure: (Respective lines are highlighted)

  • Line 39: Start with the call to recursive binary_search() function, passing the left and right limits of the list and a key to find

  • Line 16: Calculate the mid_element index, if the element at the middle index matches the key, return mid-element index

  • Line 24-25: If key is smaller than the element at the mid-element index, make the recursive call passing the left sub-list limits (left(left toto mid−1)mid-1)

  • Line 28: If the key is greater than the element at the mid-element index, make the recursive call passing the right sub-list limits (mid+1(mid+1 toto right).right).

  • Line 31: When the element is not found and the list can no longer be subdivided, then return -1, since it is an invalid index

And that’s it. When one of the recursive functions finds the element, it will return that element. Otherwise, −1 will be returned anyway

Time complexity

If we start at the middle of the list, it’s either we are lucky and the element matches or we discard half of the list. In the worst case, we will repeatedly discard half of the sublists from the previous step until the list can no longer be subdivided, i.e., it is of size 1. An array of size n can be divided into halves lg n times until we reach a sublist of size 1. Hence, the time complexity of this solution of finding an element in a sorted list is O(lgO(lg n).n).