Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c
communitycreator

How to implement a binary search using divide and conquer in C

Rithika Velicheti

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};

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.
1 of 4

Code

#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;
}

RELATED TAGS

c
communitycreator
RELATED COURSES

View all Courses

Keep Exploring