C++中二分查找递归非递归实现并分析-创新互联

C++ 中二分查找递归非递归实现并分析

二分查找在有序数列的查找过程中算法复杂度低，并且效率很高。因此较为受我们追捧。其实二分查找算法，是一个很经典的算法。但是呢，又容易写错。因为总是考虑不全边界问题。

用非递归简单分析一下，在编写过程中，如果编写的是以下的代码：

#include
#include
using namespace std;

int binaty_search(int* arr, size_t n, int x)
{ 
  assert(arr);
  int left = 0;
  int right = n - 1;

  while (left <= right)
  {
    int mid = (left + right) / 2;
    if (x < arr[mid])
    {
      right = mid-1;
    }
    else if (x > arr[mid])
    {
      left = mid+1;
    }
    else
    return mid;
  }
  return -1;
}

int main()
{
  int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 0) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 1) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 2) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 3) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 4) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 5) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 6) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 7) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 8) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 9) << endl;
  cout << binaty_search(arr, sizeof(arr) / sizeof(int), 10) << endl;
    return 0;
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。