lolsharp - 9 months ago 56

C++ Question

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:

- Find
`b`

and`c`

, the 1/3 and 2/3 intervals. (You're now doing that correctly). - If
`a[b]`

or`a[c]`

equals`key`

, then you've found the result. (You're also doing that correctly). - 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.

Source (Stackoverflow)