程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++ 中二分查找遞歸非遞歸實現並分析

C++ 中二分查找遞歸非遞歸實現並分析

編輯:關於C++

C++ 中二分查找遞歸非遞歸實現並分析。本站提示廣大學習愛好者:(C++ 中二分查找遞歸非遞歸實現並分析)文章只能為提供參考,不一定能成為您想要的結果。以下是C++ 中二分查找遞歸非遞歸實現並分析正文


C++ 中二分查找遞歸非遞歸實現並分析

投稿:lqh

這篇文章主要介紹了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, 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;
}

那麼我們可以簡單分析一下:

如果是以下這樣的代碼實現:

#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;
}

那麼可以簡單分析一下為:

同樣,遞歸實現的條件也分為兩種,我就只演示一種,代碼如下:

#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. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved