This method repetedly devides a problem into two or more problems of the same type, combining the results of the sub-problems in order to obtain the solution to the initial problem.

Example: Find the place of a number in an ordered vector with as few comparisons as possible.

Solution: First, we compare the number with the element in the middle of the vector. If the number is smaller, we do the same thing for the vector represented by the elements to the left. If the number is bigger, we do the same thing for the vector represented by the elements to the right.

Pascal prgram:

var v:array[1..100] of integer;
n,i,j,k:integer;

procedure search(a,b:integer);
var m:integer;
begin
if a>b then writeln(k, ' is not in the vector')
else
begin
m:=(a+b) div 2;
if v[m]=k then writeln('position ',m)
else if k<v[m] then search(a,m)
else search(m+1,b);
end;
end;

begin
readln(n);
for i:=1 to n do
readln(v[i]);
readln(k);
search(1,n);
end.

 

C++ program:

#include<iostream.h>
int v[100],i,j,k,n;

void search(int a, int b)
{
int m;
if (a>b) {cout<<k<<" is not an element of the vector"<<endl;}
else
{
m=(a+b)/2;
if (k==v[m]) {cout<<"position "<<m;}
else
{
if (k<v[m]) {search(a,m);}
else {search(m+1,b);}
}
}
}

void main()
{
cin>>n;
for (i=1;i<=n;i++)
cin>>v[i];
cin>>k;
search(1,n);
}