Recursive binary search in sorted array c++

Question

I have to write a recursive function which searches through a sorted array.

#include <iostream>
using namespace std;

int find(int value, int* folge, int max) {

}


int main() {
    int const n = 7;
    int wert1 = 4, wert2 = 13, wert3 = 2, wert4 = 25;
    int folge[n] = {3,4,9,13,13,17,22};
    wert1 = find(wert1, folge, n);
}

This is the part of code that was given to us and we have to finish it.
I know how to do this if you have 4 variables available. (min and max) But I only have three, is there a way to edit the start point of the array which is given to the next function?

An array name decays to a pointer in ordinary use. So where it looks like you are passing an array by name, you are really just passing an int*. You can recursively pass a modified int* by simply adding an offset to it. find(value, folge+m, max-m) — JSF
– JSF, Commented Jan 7, 2016 at 20:00
@SergeyA Wert is the number we are looking to find in the array — HW1099
– HW1099, Commented Jan 7, 2016 at 20:03
What is find supposed to return when it finds the item you want? What is it supposed to return when it doesn't find that? — JSF
– JSF, Commented Jan 7, 2016 at 20:04
Very nice question, but I recommend that you translate your variable names into English before posting a question, that makes our job a lot easier. — Armen Tsirunyan
– Armen Tsirunyan, Commented Jan 7, 2016 at 20:08

Armen Tsirunyan · Accepted Answer · 2016-01-07 20:03:09Z

3

Suppose you have your four-param version:

find(value, array, min, max);

with the three-parameter version you can call:

find(value, array + min, max);

Note that the max'th element of array is actually max-minth element of array + min, so depending on your implementation you may want to call

find(value, array + min, max - min);

answered Jan 7, 2016 at 20:03

Armen Tsirunyan

134k61 gold badges336 silver badges442 bronze badges

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

2 Comments

Ben Voigt Over a year ago

If the last argument is a count, yes. If it's an index, it needs to be adjusted when the base pointer is changed.

JSF Over a year ago

@BenVoigt in this context, a count and an index are the same thing and either way it needs to be adjusted. It also needs to be adjusted when the base isn't changed. Either way, the count is always reduced and in this three parameter form of search the count is always an index.

Vlad from Moscow · Accepted Answer · 2016-01-07 20:53:31Z

The function can be written the following way

#include <iostream>

int find( int value, int* folge, int max ) 
{
    if ( max == 0 ) return -1;

    int middle = max / 2;

    if ( folge[middle] == value ) return middle;

    bool lower = value < folge[middle];
    int n = lower ? find( value, folge, middle ) 
                  : find( value, folge + middle + 1, max - middle - 1 );

    return n != -1 && !lower ? n + middle + 1: n; 
}

int main()
{
    int const n = 7;
    int wert1 = 4, wert2 = 13, wert3 = 2, wert4 = 25;
    int folge[n] = {3,4,9,13,13,17,22};

    std::cout << wert1 << " = " << find(wert1, folge, n) << std::endl;
    std::cout << wert2 << " = " << find(wert2, folge, n) << std::endl;
    std::cout << wert3 << " = " << find(wert3, folge, n) << std::endl;
    std::cout << wert4 << " = " << find(wert4, folge, n) << std::endl;

    return 0;
}

The program output is

4 = 1
13 = 3
2 = -1
25 = -1

Or one more test program

#include <iostream>

int find( int value, int* folge, int max ) 
{
    if ( max == 0 ) return -1;

    int middle = max / 2;

    if ( folge[middle] == value ) return middle;

    bool lower = value < folge[middle];
    int n = lower ? find( value, folge, middle ) 
                                  : find( value, folge + middle + 1, max - middle - 1 );

    return n != -1 && !lower ? n + middle + 1: n; 
}

int main()
{
    int const n = 7;
    int folge[n] = {3,4,9,13,13,17,22};

    for ( int x : { 2, 3, 4, 9, 13, 17, 22, 25 } )
    {
        std::cout << x << " -> " << find( x , folge, n ) << std::endl;  
    }        

    return 0;
}

Its output is

2 -> -1
3 -> 0
4 -> 1
9 -> 2
13 -> 3
17 -> 5
22 -> 6
25 -> -1

mksteve · Accepted Answer · 2016-01-07 20:00:03Z

1

find( &folge[1],...) // ignore first element

The address of nth element is an array of size Size-n

answered Jan 7, 2016 at 20:00

mksteve

13.4k3 gold badges31 silver badges53 bronze badges

Comments

Anton Gorev · Accepted Answer · 2016-01-07 20:18:36Z

0

If folge points to the first element, then folge+1 will point to the second.

int find(int value, int* folge, int max)
{
    int m = max/2;
    if (0 == max)
    {
        return -1;
    }

    if (value == folge[m])
    {
        return value;
    }
    else if (value < folge[m])
    {
        return find(value, folge, m);
    } else
    {
        return find(value, folge + m + 1, max - m - 1);
    }
}

answered Jan 7, 2016 at 20:18

Anton Gorev

4333 silver badges14 bronze badges

1 Comment

JSF Over a year ago

Your discussion/examples of adjusting folge are correct, but your binary search logic has a few bugs.

Glenn Teitelbaum · Accepted Answer · 2016-01-07 20:48:43Z

0

You can change the value of the int pointer folge

int find(int value, int* folge, int max) {
   if (max == 0) {
        return -1;
   }

   int mid=max/2;

   if (value == folge[mid])
   {
        return mid;
   }

   int base=0;

   if (value < folge[mid])
   {
       max=mid-1;
   }
   else
   {
       max-=(mid+1);
       base=mid+1;
   }

   int ret=find(value,folge+base,max);

   if (ret == -1)
   {
       return -1;
   }

   return ret+base;
}

edited Jan 7, 2016 at 20:48

answered Jan 7, 2016 at 20:04

Glenn Teitelbaum

10.4k4 gold badges42 silver badges82 bronze badges

2 Comments

Ben Voigt Over a year ago

That last line will compile as a comma operator, probably not what you intended. Also, it is traditional for a binary search function to return the index where the item was found, not its value (which you already know). And of course, you have a problem of non-termination when max == 1, since max - max/2 doesn't decrease.

Glenn Teitelbaum Over a year ago

@BenVoigt switched to index based return and cleaned up

Collectives™ on Stack Overflow

Recursive binary search in sorted array c++

5 Answers 5

2 Comments

Comments

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

2 Comments

Comments

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related