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){
return 0;
}
printf("Found it at %d", position);
return 0;
}

RELATED TAGS

c
communitycreator

CONTRIBUTOR

Rithika Velicheti
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time