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.
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.
Binary search is all about searching for an element â€“ we can return the results as True/False
or index value/-1
(if not present).
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};
int low=0,high=9,mid,x=3;
Consider a while-loop
that will run until low variable
is low/equal
to high variable
.
Now, within the while-loop, assign the mid variable
to middle integer index â€“> mid=(low+high)/2
Now, check if x
is greater than/less than/equals to mid
x>a[mid]
, that means x is on the right side of the middle index, so we will change low=mid
.x<a[mid]
, that means x is on the left side of the middle index, so we will change high=mid
.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; }
RELATED TAGS
CONTRIBUTOR
View all Courses