lolsharp 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?

Answer

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.

I'm not going to get any more specific than this, because this sounds like an assignment and you should be writing your own code.

Comments