1

I have tried to search a data in a structure like 1D array, but it always tell me that the target data has not been found, although I have make the algorithm exactly as it is. now I am totally confused

the below is how I define function

int RecBinarySearch (int a[], int low, int high, int key) {

    int mid{ };

    if (high >= low  ) {
        mid =  low + (high-low)/2;

        if (key == a[mid]) return mid;
        if (key > a[mid]) RecBinarySearch(a, mid + 1, high, key);
        if (key < a[mid]) RecBinarySearch(a, low, mid - 1, key);
    }

    return -1;
}

and here you see how I define my array

int n{};
int* a = new int [n] {};
Improve this question
10
  • 5
    Note: remove the c tag, your code is C++, not C. Different languages, different solutions. Commented Sep 24, 2021 at 15:24
  • @LucaPolito int a[n]; in C :). RecBinarySearch is C compatible (except this mid{}), c tag should stay Commented Sep 24, 2021 at 15:25
  • @tstanisl I get your point. But in general, a C solution may not be ideal (not leveraging all the features of C++), and a C++ solution may be wrong in C. Commented Sep 24, 2021 at 15:28
  • @tstanisl int* a = new int [n] {}; is not C. int mid{ }; is not C. But it's written like you would write C code. Commented Sep 24, 2021 at 15:29
  • You should edit your question and show a minimal reproducible example. Commented Sep 24, 2021 at 15:30

2 Answers 2

Reset to default
4

When you recursively call a function that is supposed to return something, you need to return what the recursive call would return.

    if (key > a[mid]) return RecBinarySearch(a, mid + 1, high, key);
    if (key < a[mid]) return RecBinarySearch(a, low, mid - 1, key);

Okay, don't take that literally. It is true for most divide and conquer style recursive algorithms and greedy style algorithms, where the recursive call is designed to find the answer. Then, that answer has to be propagated up. There are other cases where the recursive call is just finding a portion of the solution. In those cases, the result needs to be incorporated into the final answer.

The point is, however, that you are ignoring the returned result of the recursive call, which is triggering a bug where you will return -1 instead of the answer found by the call.

Note that C++ includes binary_search (and C includes bsearch).

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

2 Comments

Thank you so much bro, so useful and that's a real point I missed really 10 Q so much
@SanaAllahKheiri Consider taking the tour.
1

This is what you want:

#include <iostream>

int RecBinarySearch(int a[], int low, int high, int key)
{
  if (high >= low)
  {
    int mid = low + (high - low) / 2;

    if (key == a[mid])
      return mid;
    if (key > a[mid])
      return RecBinarySearch(a, mid + 1, high, key);  // you forgot the return statement
    if (key < a[mid])
      return RecBinarySearch(a, low, mid - 1, key);   // you forgot the return statement
  }

  return -1;
}

int main()
{
  int values[] = { 1,3,4,5,6,7 };   // must be sorted

  // check if we find each of the values contained in values
  for (auto v : values)
  {
    if (RecBinarySearch(values, 0, 7, v) == -1)
    {
      std::cout << v << " not found\n";
    }
  }

  int valuesnotcontained[] = {0,2,8,10};

  // check we don't find values not contained in values
  for (auto v : valuesnotcontained)
  {
    if (RecBinarySearch(values, 0, 7, v) != -1)
    {
      std::cout << v << " should not be found\n";
    }
  }
}

It includes some basic test code.

Improve this answer

2 Comments

I have written that but my need is recursion
@SanaAllahKheiri but there is recursion in the code in my answer... The difference is that in my code I use the return statement, but you don't.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.