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

发布时间:2020-09-21 13:44:25 作者:lqh
来源:脚本之家 阅读:141

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

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

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

#include<iostream>
#include<assert.h>
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;
}

那么我们可以简单分析一下:

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

如果是以下这样的代码实现:

#include<iostream>
#include<assert.h>
using namespace std;

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

  while (left < right)
  {
    int mid = (left + right) / 2;
    if (x < arr[mid])
    {
      right = mid;
    }
    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;
}

那么可以简单分析一下为:

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

同样,递归实现的条件也分为两种,我就只演示一种,代码如下:

#include<iostream>
#include<assert.h>
using namespace std;

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

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

  return 0;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

推荐阅读:
  1. C++中怎么实现非递归排序
  2. c++ 搜索二叉树/排序二叉树

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++ 二分查找 递归

上一篇:Vue中的ref作用详解(实现DOM的联动操作)

下一篇:linux版本号如何确定

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》