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?

```c
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.

```c
int low=0,high=9,mid,x=3;
```
2. Consider a `while-loop` that will run until `low variable` is `low/equal` to `high variable`.
3. Now, within the while-loop, assign the `mid variable` to middle integer index **-->** `mid=(low+high)/2`

4. 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`.


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

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

Why do we use divide and conquer method?

How to solve binary search using divide and conquer

Example

Explanation

Code