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).

1 of 4

Explanation

  1. 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;

  1. Consider a while-loop that will run until low variable is low/equal to high variable.

  2. Now, within the while-loop, assign the mid variable to middle integer index –> mid=(low+high)/2

  3. Now, check if x is 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 change low=mid.
  • If x<a[mid], that means x is on the left side of the middle index, so we will change high=mid.
  • Otherwise, x==a[mid] means x is found and return 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.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)