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

Introduction to Divide and Conquer With Binary Search

Explore the divide and conquer algorithmic approach by understanding its three main steps: divide, conquer, and merge. Learn how to apply this method through binary search, a recursive algorithm that efficiently finds elements in a sorted array. Understand the time complexity and recursive process to deepen your problem-solving skills for coding interviews.

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., it 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 look at an example to grasp this concept better.

Binary search method

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

Now, we could go about searching the array in a linear manner, starting from the 0th index and checking the value at each index as we move towards the 10th index. But a fascinating property of sorted arrays 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.

Note: In sorted arrays, 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:

  • arr[i] == k, in which case we have found the key.
  • arr[i] < k, in which case the key must exist in the right subarray (considering the array is sorted in ascending order).
  • arr[i] > k, in which case the key must exist in the left subarray (considering the array is sorted in ascending order).

Visualization

The following illustration gives a quick visualization of the pseudocode above:

canvasAnimation-image
1 / 7

Code

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

C# 9.0
using System;
class Program
{
    // Below is a binary search method implemented recursively
    // If the required element, x, is in the given array, arr, its location will be returned
    // Otherwise, if the element is not in the array, -1 will be returned
    /// <summary>
    /// Finds a key in the array.
    /// </summary>
    /// <param name="arr">Array of integers.</param>
    /// <param name="left">Left index of the array.</param>
    /// <param name="right">Right index of the array.</param>
    /// <param name="key">An integer to find in the array.</param>
    /// <returns>The index of the key in the array if found, -1 otherwise.</returns>
    public static int BinarySearch(int[] arr, int left, int right, int key)
    {
        if (right >= left)
        {
            int midElement = left + (right - left) / 2;
            // If the required element is found at the middle index
            if (arr[midElement] == key)
            {
                return midElement;
            }
            // If the required element is smaller than the element at the middle index
            // It can only be present in the left sub-array
            if (arr[midElement] > key)
            {
                return BinarySearch(arr, left, midElement - 1, key);
            }
            // Otherwise, it would be present in the right sub-array
            return BinarySearch(arr, midElement + 1, right, key);
        }
        // If the element is not in the array
        return -1;
    }
    // Driver code to test above method
    public static void Main()
    {
        int[] arr = { 2, 4, 7, 25, 60 };
        int key = 25; // to find, feel free to change this
        int result = BinarySearch(arr, 0, arr.Length - 1, key);
        if (result == -1)
        {
            Console.WriteLine("Element is not present in the array");
        }
        else
        {
            Console.WriteLine("Element is present at index: " + result);
        }
    }
}

Explanation

Here, binary search is implemented recursively. If the required key is found in the given array arr, the index is returned. Otherwise, if the key is not found, −1 is returned anyway.

As explained in the visualization above, the code follows this procedure:

  • Line 51: We start with the call to the recursive BinarySearch() method, passing the left and right limits of the array and a key to find.

  • Line 22: We calculate the midElement index if the element at the middle index matches the key and return the midElement index.

  • Lines 32–35: If key is smaller than the element at the midElement index, we make the recursive call passing the left subarray limits (left(left toto mid−1)mid-1).

  • Line 38: If key is greater than the element at the midElement index, we make the recursive call passing the right subarray limits (mid+1(mid+1 toto right)right).

  • Line 42: When the element is not found, and the array can no longer be subdivided, we 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 array, it’s either we are lucky and the element matches, or we discard half of the array. In the worst case, we will repeatedly discard half of the subarrays from the previous step until the array can no longer be subdivided, i.e., it is of size 11. An array of size nn can be divided into halves log⁡n\log n times until we reach a subarray of size 11. Therefore, the time complexity of this solution of finding an element in a sorted array is O(log⁡n)O(\log n).