lolsharp - 2 months ago 8
C++ Question

# c++ binarysearch divide and conquer

Instead of comparing with the midpoint design a binarysearch algorithim that compares the item you are looking for with one at the 33th percentile and the 66th percentile using recursion.

This is what I have so far

``````#include <iostream>
using namespace std;
//binary search recursion

int binarysearch(int begin, int end, int a[], int key);

void main()
{

const int size= 10;

int a[size] = { 22,32,45,55,65,75,90,100 };

cout<<binarysearch(0, 7,a, 90);

}

int binarysearch(int begin,int end,int a[],int key)
{
int b = begin+(end-begin) * (1.0/3.0);
int c = begin +( end-begin)*(2.0 / 3.0);

if (begin > end)
{
return -1;
}
if (a[b] == key)
{
cout << "b is the key";
return b;
}
if (a[c] == key)
{
cout << "c is the key";
return c;
}

if (a[begin] < key&&a[b]>key)
{
return binarysearch(begin, b-1, a, key);

}

if (a[b ] < key&&a[c ]>key)
{

return binarysearch(b + 1, c - 1, a, key);
}

if (a[c ] < key&&a[end]>key)
{

return binarysearch(c + 1, end, a, key);

}
``````

}

}
Is this right any suggestions?

Your recursion logic is still off. You don't need the `begin2` and `end2` arguments; they just add clutter and serve no useful purpose. Your logic should go like this:
1. Find `b` and `c`, the 1/3 and 2/3 intervals. (You're now doing that correctly).
2. If `a[b]` or `a[c]` equals `key`, then you've found the result. (You're also doing that correctly).
3. Otherwise, decide which of the three intervals `key` might be in. The three possibilities are [`begin`, `b-1`], [`b+1`, `c-1`], and [`c+1`, `end`]. Recurse accordingly. (This is the part that you are not doing correctly.)
You should also add one more piece of logic: if `begin > end`, then the key is not in `a` at all.