How to implement a binary search using divide and conquer in C
The strategy behind divide and conquer method is to solve a problem where n inputs are split into many small subproblems and then each subproblem is solved and combined to find the solution of each subproblem. The solution of each subproblem then results in a solution to the original problem.
Why do we use divide and conquer method?
We use the divide and conquer method because it can be difficult to solve a problem with n inputs. So, we divide it into subproblems until it is easy to get a solution, and then we combine all solutions of the divided subproblem into one.
How to solve binary search using divide and conquer
Binary search is all about searching for an element – we can return the results as True/False or index value/-1(if not present).
Example
Let’s look at an example. Say there is an array of size 10 that contains integers in ascending order.
Can you find if 3 is there or not?
int a[10]={1,3,5,7,9,11,13,15,17,21};
First, grasp the logic of the divide and conquer technique visually for finding a target value (x=3).
Explanation
- First take 3 variables in which the first integer index, last integer index, and middle integer index value of array/sub-array are stored and then use another variable to store the given integer to be found.
int low=0,high=9,mid,x=3;
-
Consider a
while-loopthat will run untillow variableislow/equaltohigh variable. -
Now, within the while-loop, assign the
mid variableto middle integer index –>mid=(low+high)/2 -
Now, check if
xis greater than/less than/equals to mid
- If
x>a[mid], that means x is on the right side of the middle index, so we will changelow=mid. - If
x<a[mid], that means x is on the left side of the middle index, so we will changehigh=mid. - Otherwise,
x==a[mid]meansx is foundandreturn True.
Code
Let’s implement the logic for binary search using divide and conquer in C
#include<stdio.h>int binary_search(int A[], int key, int len) {int low = 0;int high = len -1;while (low <= high) {int mid = low + ((high - low) / 2);if (A[mid] == key) {return mid;}if (key < A[mid]) {high = mid - 1;}else {low = mid + 1;}}return -1;}int main() {int a[10]={1,3,5,7,9,11,13,15,17,21};int key = 3;int position = binary_search(a, key, 10);if (position == -1){printf("Not found");return 0;}printf("Found it at %d", position);return 0;}
The binary_search function takes an array, the target value, and the array length as parameters, then iteratively searches for the target using a divide-and-conquer approach. If the target is found, it returns its position; otherwise, it returns -1. In the main function, a sample array is initialized, and the binary_search function is called to find the position of the key value (3 in this case). If found, it prints the position; otherwise, it prints Not found.
Test yourself
Given an array sorted in descending order, such as {21, 17, 15, 13, 11, 9, 7, 5, 3, 1}, challenge yourself to modify the following code to efficiently locate a specific target value within the array.
#include <stdio.h>int binary_search(int A[], int key, int len) {int low = 0;int high = len - 1;while (low <= high) {int mid = low + ((high - low) / 2);if (A[mid] == key) {return mid;}if (key < A[mid]) {high = mid - 1;}else {low = mid + 1;}}return -1;}
