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] {};

CodePudding user response：

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).

CodePudding user response：

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.

CodePudding user response：

    return (key == a[mid])
           ? mid:
           (key > a[mid])
           ? RecBinarySearch(a, mid, high, key):
           (key < a[mid]) 
           ?RecBinarySearch(a, low, mid, key):
           -1;

Of course, supposing that a[] is correctly sorted.