Recursive Binary Search C++ without if-else statement

Question

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));
}

How do you tell if it's your middle element without one if statement? — MeetTitan
– MeetTitan, Commented Apr 23, 2016 at 16:46
@MeetTitan a[size/2] represents the middle element in every recursive call. My fault I meant isMember. — yanis
– yanis, Commented Apr 23, 2016 at 16:54
"Middle element" is ill-defined if you have an even number of elements. — Lightness Races in Orbit
– Lightness Races in Orbit, Commented Apr 23, 2016 at 16:55
You have a problem when size is odd – for instance, when it is 3, you will divide into a + 1 with size 1, and a with size 1. a[2] has gone missing. — molbdnilo
– molbdnilo, Commented Apr 23, 2016 at 16:58

Sam Varshavchik · Accepted Answer · 2016-04-23 16:53:58Z

3

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:

answered Apr 23, 2016 at 16:53

Sam Varshavchik

119k6 gold badges109 silver badges164 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Vucko Over a year ago

haha no if, only ternary operator :D nice, nice, I like it.

yanis Over a year ago

Changing the parameters in the method from the question it works without the ternary operator as well.

Sam Varshavchik Over a year ago

You can't change the question. If you want to change the requirements, ask a new question (yes, it's easy to do it without the ternary operator also).

yanis Over a year ago

No, no I just explain to @Vucko that it works without ternary operator too. Thank you Sam.

Vucko Over a year ago

@samVarshavchik I know bro, it just sheer joy I feel when I see an answer like this :D

Collectives™ on Stack Overflow

Recursive Binary Search C++ without if-else statement

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related