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 array.
We'll cover the following
Divide and conquer method
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 together. Therefore, divide and donquer solutions have the following three steps:
- Divide
- Conquer
- Merge
Let’s take an example to grasp this concept better.
Example: Binary search
Consider a sorted array arr
, of n
integers, and 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
. However, a fascinating property of sorted arrays is that regardless of the element we are looking at, we can be sure that the next element has either a value greater than or equal to the current element and the previous element has either a value lesser than or equal to the current element.
In sorted arrays, the value at index
i+1
is greater than or equal to the element at indexi
, and the value at indexi-1
is lesser than or equal to the element at indexi
.
How can we use this property? If we are looking for a key k
in the array (considering the array is sorted in ascending order) at any particular index i
, there are three possibilities:
arr[i] == k
, when the key is foundarr[i] < k
, where the key must exist in the right subarrayarr[i] > k
, where the key must exist in the left subarray
Time complexity
If we start in the middle of the array, either we are lucky and the element matches or we discard half of the array. In the worst case, we repeatedly discard half of the sub-arrays from the previous step until the array can no longer be subdivided, i.e., it is of size 1. An array of size n can be divided into halves times until we reach a subarray of size 1. Hence, the time complexity of finding an element in a sorted array using this technique is .
Visualization
Code
class DivideAndConquer {public static int BinarySearch(int arr[], int left, int right, int key) {if (right >= left) {int MidElement = left + (right - left) / 2;if (arr[MidElement] == key) // If the required element is found at the middle indexreturn MidElement;if (key < arr[MidElement]) // If the required element is smaller than the element at the middle index It can only be present in the left subarrayreturn BinarySearch(arr, left, MidElement - 1, key);return BinarySearch(arr, MidElement + 1, right, key); // else, it would be present in the right subarray}return -1; // Element not found, and the array can not be further divided.}public static void main(String args[]) {int arr[] = { 3, 5, 7, 15, 25 };int key = 7; // to find, feel free to change thisint result = BinarySearch(arr, 0, arr.length - 1, key);if (result != -1)System.out.println("Key " + "\"" + key + "\" found at index = " + result);elseSystem.out.println("Key " + "\"" + key + "\"not found!");key = 0; // Trying for a different valueresult = BinarySearch(arr, 0, arr.length - 1, key);if (result != -1)System.out.println("Key " + "\"" + key + "\" found at index = " + result);elseSystem.out.println("Key " + "\"" + key + "\"not found!");}}
Explanation
Here, binary search is implemented recursively. If the required key is found in the given array arr
, 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 24: Start with the call to recursive
binarySearch()
function, passing theleft
andright
limits of the array and akey
to find. -
Lines 7-9: Calculate the
MidElement
index. If the element at the middle index matches thekey
, return theMidElement
index. -
Lines 11-12: If
key
is smaller than the element at theMidElement
index, make the recursive call passing the left subarray limits (). -
Line 14: If
key
is greater than the element at theMidElement
index, make the recursive call passing the right subarray limits (). -
Line 16: When the element is not found and the array can no longer be subdivided, then return
-1
since it is an invalid index.
That’s it! When one of the recursive functions finds the element, it returns that element. Otherwise, -1
is returned anyway.