欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++ 中二分查找遞歸非遞歸實(shí)現(xiàn)并分析

 更新時間:2017年06月06日 09:23:30   投稿:lqh  
這篇文章主要介紹了C++ 中二分查找遞歸非遞歸實(shí)現(xiàn)并分析的相關(guān)資料,需要的朋友可以參考下

C++ 中二分查找遞歸非遞歸實(shí)現(xiàn)并分析

二分查找在有序數(shù)列的查找過程中算法復(fù)雜度低,并且效率很高。因此較為受我們追捧。其實(shí)二分查找算法,是一個很經(jīng)典的算法。但是呢,又容易寫錯。因?yàn)榭偸强紤]不全邊界問題。

用非遞歸簡單分析一下,在編寫過程中,如果編寫的是以下的代碼:

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

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

榪欓噷鍐欏浘鐗囨弿榪? title=

如果是以下這樣的代碼實(shí)現(xiàn):

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

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

榪欓噷鍐欏浘鐗囨弿榪? title=

同樣,遞歸實(shí)現(xiàn)的條件也分為兩種,我就只演示一種,代碼如下:

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

感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!

相關(guān)文章

  • 解析C++中的for循環(huán)以及基于范圍的for語句使用

    解析C++中的for循環(huán)以及基于范圍的for語句使用

    這篇文章主要介紹了解析C++中的for循環(huán)以及基于范圍的for語句使用,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下
    2016-01-01
  • C++使用循環(huán)計(jì)算標(biāo)準(zhǔn)差的代碼實(shí)現(xiàn)

    C++使用循環(huán)計(jì)算標(biāo)準(zhǔn)差的代碼實(shí)現(xiàn)

    在C++中,計(jì)算標(biāo)準(zhǔn)差可以使用循環(huán)來實(shí)現(xiàn),本文給大家介紹了一個示例代碼,演示了如何使用循環(huán)計(jì)算標(biāo)準(zhǔn)差,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,需要的朋友可以參考下
    2023-12-12
  • C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹堆

    C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹堆

    這篇文章主要為大家介紹了C語言植物大戰(zhàn)數(shù)據(jù)結(jié)構(gòu)二叉樹堆的圖文示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-05-05
  • 簡單談?wù)凜++ 中指針與引用

    簡單談?wù)凜++ 中指針與引用

    下面用通俗易懂的話來概述一下,指針-對于一個類型T,T*就是指向T的指針類型,也即一個T*類型的變量能夠保存一個T對象的地址,而類型T是可以加一些限定詞的,引用-引用是一個對象的別名,主要用于函數(shù)參數(shù)和返回值類型,符號X&表示X類型的引用。
    2015-09-09
  • C++可視化角色按鍵移動控制的實(shí)現(xiàn)

    C++可視化角色按鍵移動控制的實(shí)現(xiàn)

    這篇文章主要介紹了C++可視化角色按鍵移動控制的實(shí)現(xiàn),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2020-03-03
  • C語言中雙向鏈表和雙向循環(huán)鏈表詳解

    C語言中雙向鏈表和雙向循環(huán)鏈表詳解

    這篇文章主要介紹了C語言中雙向鏈表和雙向循環(huán)鏈表詳解的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • C語言?柔性數(shù)組的使用詳解

    C語言?柔性數(shù)組的使用詳解

    柔性數(shù)組(Flexible?Array)是引入的一個新特性,它允許你在定義結(jié)構(gòu)體時創(chuàng)建一個空數(shù)組,而這個數(shù)組的大小可以在程序運(yùn)行的過程中根據(jù)你的需求進(jìn)行更改特別注意的一點(diǎn)是:這個空數(shù)組必須聲明為結(jié)構(gòu)體的最后一個成員,并且還要求這樣的結(jié)構(gòu)體至少包含一個其他類型的成員
    2022-03-03
  • 一元多項(xiàng)式加法運(yùn)算

    一元多項(xiàng)式加法運(yùn)算

    今天小編就為大家分享一篇關(guān)于一元多項(xiàng)式加法運(yùn)算,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來看看吧
    2019-03-03
  • 關(guān)于C語言和命令行之間的交互問題

    關(guān)于C語言和命令行之間的交互問題

    這篇文章主要介紹了C語言和命令行之間的交互,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-07-07
  • C語言實(shí)現(xiàn)隨機(jī)讀寫文件的函數(shù)詳解

    C語言實(shí)現(xiàn)隨機(jī)讀寫文件的函數(shù)詳解

    文件的隨機(jī)讀寫,可以在文件中指定的任意位置讀或者寫。這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)隨機(jī)讀寫文件的3個函數(shù),感興趣的可以了解一下
    2023-03-03

最新評論