我想要一个递归函数来使用二进制搜索检查数组的顺序

Question

我写了一个递归函数来检查大小为 n 的数组是否按升序排列：

bool sortedAscending(const int*x, int n){
if (n == 0) return true;
if (x[n - 1] >= x[n - 2]) sortedAscending(x, n - 1);
else return false;
}

我想做同样的工作，但使用二进制搜索算法（即将每次递归调用将数组分成两半......）。我怎样才能做到这一点？谢谢。

Answer 1

bool sortedAscending(const int* x, int n) {
  if (n <= 1) return true;
  int m = n / 2;
  return x[m-1] <= x[m] &&
         sortedAscending(x, m) &&
         sortedAscending(x + m, n - m);
}

Answer 2

我更喜欢使用指向候选数组开始和结束的指针。这样更符合迭代器风格。

#include <iostream>

bool sortedAscending(const int* start, const int* end)
{
    if(start == end) return true;
    if(start + 1 == end) return true;
    auto halfDiff = (end - start) / 2;
    return *(start + halfDiff - 1) <= *(start + halfDiff) && sortedAscending(start, start + halfDiff) && sortedAscending(start + halfDiff, end);
}

int main()
{
    int array1[] = {0,1,2,3,4,5,6,7};
    int array2[] = {0,1,3,2,4,5,6,7};
    int array3[] = {0};
    int* array4 = nullptr;

    std::cout << "Array1: " << sortedAscending(std::begin(array1), std::end(array1)) << std::endl;
    std::cout << "Array2: " << sortedAscending(std::begin(array2), std::end(array2)) << std::endl;
    std::cout << "Array3: " << sortedAscending(std::begin(array3), std::end(array3)) << std::endl;
    std::cout << "Array4: " << sortedAscending(array4, array4) << std::endl;

    return 0;
}

我想要一个递归函数来使用二进制搜索检查数组的顺序

I want a recursive function to check the order of an array using binary search

c++

recursion

binary-search