Finding index of target using recursive binary search in C

Question

I'm only allowed to use the given parameters. I can't wrap my head around the thought of finding the index of the target. Any ideas?

#include <stdio.h>

int RecBinarySearch(int arr[], int len, int target) {

    if (len <= 0)
        return 0; 

    int mid = len/2;

    if (target == arr[mid]){
        return 1;
    }
    if (target < arr[mid]){
        int i=0;
        return RecBinarySearch(arr, mid, target);
    }

    else {
        return RecBinarySearch(arr+mid+1, len-mid-1, target);
    }
}

int main(void){
    int arr[6]={1,2,3,4,5,6};
    int len=sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    RecBinarySearch(arr,len,target);
}

So this code will return the target value, but I need to find which position it is in. In this case since the target is 5, it should return 4. — McBonzo
– McBonzo, Commented Mar 1, 2018 at 6:46
.I can't wrap my head around how I could find the index because I can't increment anything with the given parameters - Explain the bold part. — user2736738
– user2736738, Commented Mar 1, 2018 at 6:46
What problem do you have with the code you show? Does it work? Perhaps you should return mid when the target is found? And return e.g. -1 when not found? — Some programmer dude
– Some programmer dude, Commented Mar 1, 2018 at 6:47
@coderredoc I just realized that it wouldnt work even if I incremented something by putting in a parameter. Let me delete that part. Someprogrammerdude, The code works but I'm trying to find the index of the target, but I don't know how to start. — McBonzo
– McBonzo, Commented Mar 1, 2018 at 6:52

Rahul Jain · Accepted Answer · 2018-03-01 06:57:23Z

1

Ideone link

#include <stdio.h>
int RecBinarySearch(int arr[], int len, int target) {
    if(len <= 0) return -1;
    int mid = len / 2;
    if(arr[mid] == target) return mid;
    if(arr[mid] < target) {
        int rightIndex = RecBinarySearch(arr+mid+1, len-mid-1, target);
        return rightIndex == -1 ? -1 : mid+rightIndex+1;
    } else {
        int leftIndex = RecBinarySearch(arr, mid, target);
        return leftIndex == -1 ? -1 : leftIndex;
    }
}

int main(void){
    int arr[6]={1,2,3,4,5,6};
    int len=sizeof(arr)/sizeof(arr[0]);
    int target = 5;
    printf("%d", RecBinarySearch(arr,len,target));
}

answered Mar 1, 2018 at 6:57

Rahul Jain

3572 silver badges17 bronze badges

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

2 Comments

McBonzo Over a year ago

Can you explain to me what return rightIndex == -1 ? -1 : mid+rightIndex+1; does?

Rahul Jain Over a year ago

-1 is to denote that the target is not present in the array. rightIndex comes from recursion. If it comes -1, so it means the target is not found and we have to return -1 too.

Camion · Accepted Answer · 2018-03-01 06:58:51Z

1

1st : you don't really need recursivity in this goal. You might more efficiently replace it with a loop, using left and right marker (recursivity is quite expensive for various reasons).

2nd : Instead of returning 0 or 1, which you don't use, you should return mid or -1 if not found, and since you shifted your array in the recursive call (passing array+mid+1), you should add the shift value to the return value, and then you get the position in the return value in main.

edited Mar 1, 2018 at 6:58

answered Mar 1, 2018 at 6:51

Camion

1,39411 silver badges26 bronze badges

Comments

cse · Accepted Answer · 2018-03-01 07:13:59Z

1

Given that, I'm only allowed to use the given parameters, you can use following. See it working here:

int BinarySearch(int arr[], int len, int target) {
    int startI = 0, endI = len-1;

    while(startI<=endI)
    {
        int mid= (startI+endI)/2;
        if(arr[mid] == target)
            return mid;
        if(arr[mid] < target)
        {
            startI = mid +1;        
        }
        else
        {
            endI = mid -1;
        }
    }
    return -1;
}

answered Mar 1, 2018 at 7:13

cse

4,1042 gold badges23 silver badges38 bronze badges

3 Comments

vgru Over a year ago

This isn't recursive though.

cse Over a year ago

@Groo Yaa... But this is not mentioned in the OP post that it must be a recursive solution. That's why I mentioned that Given that, I'm only allowed to use the given parameters.

Yasushi Shoji Over a year ago

@cse the question isn't the best but the title says "using recursive binary search in C".

Collectives™ on Stack Overflow

Finding index of target using recursive binary search in C

3 Answers 3

2 Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related