C语言数据结构中二分查找递归非递归实现并分析

发布时间：2020-12-16 05:12:32 所属栏目：百科来源：网络整理

导读：C语言数据结构中二分查找递归非递归实现并分析前言：二分查找在有序数列的查找过程中算法复杂度低，并且效率很高。因此较为受我们追捧。其实二分查找算法，是一个很经典的算法。但是呢，又容易写错。因为总是考虑不全边界问题。用非递归简单分析一下，在

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,1) << endl;
  cout << binaty_search(arr,2) << endl;
  cout << binaty_search(arr,3) << endl;
  cout << binaty_search(arr,4) << endl;
  cout << binaty_search(arr,5) << endl;
  cout << binaty_search(arr,6) << endl;
  cout << binaty_search(arr,7) << endl;
  cout << binaty_search(arr,8) << endl;
  cout << binaty_search(arr,9) << endl;
  cout << binaty_search(arr,10) << endl;
    return 0;
}

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

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

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

int binaty_search(int* arr,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,10) << endl;
    return 0;
}

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

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

#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,left + 1,right);
    }
  }
  return -1;
}

int main()
{
  int arr[] = { 0,9 };
  cout << binaty_srarch(arr,(sizeof(arr) / sizeof(int)) - 1) << endl;
  cout << binaty_srarch(arr,9,10,(sizeof(arr) / sizeof(int)) - 1) << endl;

  return 0;
}

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!