CODEWITHSUNDEEP
c++algorithmrecursionbinary-search
yanis
yanis

Reputation: 333

Recursive Binary Search C++ without if-else statement

I am trying to implement recursive binary search in C++. However my algorithm cannot find the last two elements from the test array.I know that I am missing something. I have searched a lot for such a implementation of binary search algorithm but without success. Can anyone help me with it?

 bool isMember (int x, int a[], int size){
    if (size == 0) return false;
    return a[size/2] == x ||
          (a[size/2] < x && isMember (x,a+size/2,(size)/2)) ||
          (a[size/2] > x && isMember (x,a,(size)/2));
}

Upvotes: 0

Views: 325

Answers (1)

Sam Varshavchik
Sam Varshavchik

Reputation: 118300

No if statements here:

#include <iostream>

bool isMember (int x, int a[], int size)
{
    return size == 0 ? false
         : a[size/2] == x ? true
         : a[size/2] > x ? isMember(x, a, size/2)
         : isMember(x, a+size/2+1, size-(size/2+1));
}

int main()
{
    int v[]={1,2,4,8,16};

    for (int i=0; i<20; ++i)
        std::cout << i << ": " << isMember(i, v, 5) << std::endl;
    return 0;
}

Output:

0: 0
1: 1
2: 1
3: 0
4: 1
5: 0
6: 0
7: 0
8: 1
9: 0
10: 0
11: 0
12: 0
13: 0
14: 0
15: 0
16: 1
17: 0
18: 0
19: 0

Upvotes: 3

Related Questions