青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

那誰的技術博客

感興趣領域:高性能服務器編程,存儲,算法,Linux內核
隨筆 - 210, 文章 - 0, 評論 - 1183, 引用 - 0
數據加載中……

二分查找算法(迭代和遞歸版本)

Bentley在他的著作《Writing Correct Programs》中寫道,90%的計算機專家不能在2小時內寫出完全正確的二分搜索算法。
我自己嘗試了一下,確實要第一次就完全寫正確不容易.以下兩份實現依次為迭代和遞歸版本的代碼,二分查找的思想很多人都清楚,但是這里有一個細節就是要注意邊界的選擇.


int search(int array[], int n, int v)
{
    
int left, right, middle;

    left 
= 0, right = n - 1;

    
while (left <= right)
    {
        middle 
= (left + right) / 2;
        
if (array[middle] > v)
        {
            right 
= middle - 1;
        }
        
else if (array[middle] < v)
        {
            left 
= middle + 1;
        }
        
else
        {
            
return middle;
        }
    }

    
return -1;
}

int search_recurse(int array[], int low, int high, int v)
{
    
int middle;

    middle 
= (low + high) / 2;

    
if (low < high)
    {
        
if (array[middle] > v)
        {
            
return search_recurse(array, low, middle, v);
        }
        
else if (array[middle] < v)
        {
            
return search_recurse(array, middle + 1, high, v);
        }
        
else
        {
            
return middle;
        }
    }
    
else if (low == high)
    {
        
if (array[middle] == v)
        {
            
return middle;
        }
        
else
        {
            
return -1;
        }

    }
    
else
    {
        
return -1;
    }

    
return -1;
}

int main()
{
    
int array[] = {012345671319};

    
int m = search(array, sizeof(array)/sizeof(array[0]), 13);

    printf(
"m = %d\n", m);

    m 
= search_recurse(array, 0sizeof(array)/sizeof(array[0])13);

    printf(
"m = %d\n", m);

    
return 0;
}


posted on 2009-02-28 19:36 那誰 閱讀(18374) 評論(15)  編輯 收藏 引用 所屬分類: 算法與數據結構

評論

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

二分查找原理簡單,甚至小學生都能明白。不過這查找算法好多大學生都寫不好。沒辦法,編程這東西,很討厭。不過,要吃飯呵。
2009-03-01 13:58 |

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

應該是sizeof(array)/sizeof(array[0])
2009-03-01 14:46 | 阿郎

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

其實,上面的代碼還是有問題——兩個int值相加可能溢出。。。
2009-03-01 22:19 | Joshua Zhu

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

middle = (low + high) / 2;
這個變成 middle = low + ((hight - low) / 2), 在代碼之美里看到的。
其實這樣也行吧。 middle = low/2 + hight/2 就是慢一點兩次除法運算
2009-03-05 19:08 | reeze

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

@reeze:
同學,middle = low/2 + hight/2是不對滴。因為它的效果相當于 floor(low / 2) + floor(hight / 2)。
2009-03-07 09:44 | Joshua Zhu

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

search_recurse(array, low, middle, v);
這句可以改成
search_recurse(array, low, middle-1, v);
吧?
2009-09-20 23:42 | fzj

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

你的迭代法也不對
2010-09-09 11:15 | 錢文武

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

學習了
2011-04-14 18:49 | bubble

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

這個實現有BUG,找不到第一個和最后一個數據,最后不應該RETURN -1,應該再比較一次
2011-12-08 20:30 | zlc

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

把 int search_recurse(int array[], int low, int high, int v)中的
else if (low == high)
{
if (array[middle] == v)
{
return middle;
}
else
{
return -1;
}

}
else
{
return -1;
}
去掉,接著把上面的if (low < high)的if改為while,一樣可以執行。

完整代碼:
int search_recurse(char *arr,int value,int n)
{
int min = 0; //設置最小值為0
int max = n - 1; //設置最大值為n - 1;
int mid;
int pos = -1; //位置初始化為-1
while(min < max)
{
mid = min + (max - min)/ 2; //將字符串折半
if(arr[mid] > value) //如果中間的值大于要查找的值,則在小的一半中查找
max = mid - 1;
else if(arr[mid] < value) //如果中間的值小于要查找的值,則在大的一半中查找
min = mid + 1;
else //如果找到記錄下位置
{
pos = mid;
max = mid - 1; //再在小的一半中繼續查找
}
}
if(arr[min] == value) //如果是第一個字符等于要查找的值,記下位置
pos = min;
return pos; //返回值
}
2012-03-16 21:31 | 莫蕭

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

上面的“完整代碼”部分手誤復制錯了。不過這段代碼也是可行的,不是遞歸而已。
本來的完整代碼代碼:

int search_recurse(int arr[], int low, int high, int key)
{
int mid;

mid = (low + high) / 2;
while (low < high)
{
if (arr[mid] > key)
{
return BinSearch(arr, low, mid, key);
}
else if (arr[mid] < key)
{
return BinSearch(arr, mid + 1, high, key);
}
else
{
return mid;
}
}

return -1;
}
2012-03-16 21:34 | 莫蕭

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

@zlc
博主在循環條件中使用的是“<=”,是可以遍歷到第一個和最后一個元素的。
2012-10-05 09:57 | 孫磊磊

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

測試環境:vs2005+XP
// test.cpp : 定義控制臺應用程序的入口點。
//
#include "stdafx.h"
#include <conio.h>
#include <cstdlib>
#include <stdlib.h>
#include <iostream>
#include <bitset> //為了能夠用std::bitset
#include <limits>

#include <time.h>
using namespace std;


#include<assert.h>

//二分查找算法,前提是這個數組要是排好序的!
//先假設是int數組,返回值表示數組的下標。
//(1)迭代算法
int gezb_bsearch(int Source[], int Len, int Key)
{
int low=0,high=Len-1;
while(low<=high)
{
std::cout<<"low["<<low<<"]="<<Source[low]<<",high["<<high<<"]="<<Source[high]<<std::endl;
//if (Key<Source[low] || Key>Source[high])
//{
// std::cout<<"can't find ! key="<<Key<<",low["<<low<<"]="<<Source[low]<<",high["<<high<<"]="<<Source[high]<<std::endl;
// break;
//}
int middle = (low + high)/2;
if (Key==Source[middle])
{
std::cout<<"ok get it. \ncurIndex="<<middle<<", key="<<Key<<std::endl;
return middle;
}
else if (Key>Source[middle])
{
low = middle+1;
}
else if (Key<Source[middle])
{
high = middle-1;
}
}
return -1;
}

//(2)遞歸算法
int gezb_bsearch_recurse(int Source[],int Low,int High,int Key)
{
int middle;
if (Low<=High)
{
std::cout<<"low["<<Low<<"]="<<Source[Low]<<",high["<<High<<"]="<<Source[High]<<std::endl;
middle = (Low+High)/2;
if (Source[middle]==Key)
{
std::cout<<"ok get it. \ncurIndex="<<middle<<", key="<<Key<<std::endl;
return middle;
}
else if (Source[middle]>Key)
{
return gezb_bsearch_recurse(Source,Low,middle-1,Key);
}
else if (Source[middle]<Key)
{
return gezb_bsearch_recurse(Source,middle+1,High,Key);
}
}
return -1;
}


#define MAXLEN 10000
void main(void)
{
int arr[MAXLEN];
memset(arr,0,sizeof(arr));
for (int i=0;i<MAXLEN;++i)
{
arr[i]=(i+1)*2;
}
int key=arr[7777];
int iLen = sizeof(arr) / sizeof(arr[0]);

#if 0
//迭代算法
int index = gezb_bsearch(arr,iLen-1,key);
std::cout<<index<<std::endl;
#endif

#if 1
//遞歸算法
int index = gezb_bsearch_recurse(arr,0,iLen-1,key);
std::cout<<index<<std::endl;
#endif

system("PAUSE");
}

2013-03-31 01:18 | gezb

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

有問題請與我聯系。qq:275916517
2013-03-31 01:20 | gezb

# re: 二分查找算法(迭代和遞歸版本)  回復  更多評論   

針對迭代算法的調用處稍做修改:
#if 0
//迭代算法
int index = gezb_bsearch(arr,iLen,key);//之前iLen-1是錯誤的!!!
std::cout<<index<<std::endl;
#endif
2013-03-31 02:05 | gezb
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国产一区二区三区在线观看视频 | 国产精品视频免费观看www| 亚洲一区中文| 欧美亚洲综合在线| 欧美区一区二区三区| 国产亚洲人成网站在线观看| 欧美一区二区三区免费视频| 亚洲主播在线播放| 国产精品实拍| 99精品热视频| 亚洲国产欧美一区二区三区丁香婷| 日韩一二在线观看| 欧美激情第五页| 夜夜爽夜夜爽精品视频| 亚洲美女在线视频| 欧美日韩成人综合在线一区二区 | 亚洲精品免费在线播放| 牛牛影视久久网| 亚洲精品欧美| 亚洲精品一区在线| 欧美日本在线观看| 亚洲免费视频观看| 午夜欧美大尺度福利影院在线看| 国产老肥熟一区二区三区| 欧美一区国产一区| 榴莲视频成人在线观看| 99视频一区| 亚洲网站视频| 韩国女主播一区二区三区| 久久一区国产| 欧美激情一区二区三区全黄 | 国产精品hd| 性久久久久久久| 久久久久久久成人| 99视频+国产日韩欧美| 中日韩午夜理伦电影免费| 国产视频久久久久久久| 欧美激情网友自拍| 欧美三区美女| 欧美在线视频一区| 蜜臀久久久99精品久久久久久| 一区二区高清在线| 欧美综合国产| 日韩视频免费观看高清在线视频 | 亚洲综合色婷婷| 欧美在线视频一区| 亚洲精品视频二区| 性做久久久久久| 国产精品99久久不卡二区| 欧美伊久线香蕉线新在线| 一本不卡影院| 久久久亚洲人| 香蕉尹人综合在线观看| 欧美好吊妞视频| 久久久精品一区| 欧美色中文字幕| 久久高清国产| 欧美成人嫩草网站| 亚洲一区二区精品在线观看| 国产欧美日本| 一本色道久久综合精品竹菊| 亚洲激情图片小说视频| 香蕉精品999视频一区二区| 一区二区三区四区五区精品| 亚洲欧美影院| 在线视频国产日韩| 亚洲欧美在线aaa| 亚洲午夜成aⅴ人片| 欧美国产日本韩| 欧美xart系列高清| 国产视频在线一区二区| 夜夜爽av福利精品导航| 亚洲欧洲一二三| 久久久人成影片一区二区三区| **网站欧美大片在线观看| 欧美一区二区性| 欧美一区激情| 国产欧美日韩视频在线观看 | 亚洲欧美国产77777| 欧美不卡视频一区| 欧美二区不卡| 亚洲国产精品成人| 久久综合中文色婷婷| 久久久久国产精品午夜一区| 国产日产欧产精品推荐色| 亚洲一区一卡| 亚洲午夜在线观看| 欧美人交a欧美精品| 亚洲美女在线一区| 日韩特黄影片| 免费观看成人www动漫视频| 美日韩在线观看| 国产日本精品| 久久九九热re6这里有精品| 久久欧美肥婆一二区| 国产精品九九| 亚洲欧美久久久| 久久九九国产| 国产热re99久久6国产精品| 欧美一级艳片视频免费观看| 久色成人在线| 国产一区二区三区日韩| 午夜精品理论片| 久久久久国产精品厨房| 国产视频在线观看一区二区三区 | 久久国产一区二区三区| 伊人精品视频| 你懂的视频一区二区| 亚洲美女在线观看| 久久精品91| 99re8这里有精品热视频免费| 欧美日韩在线一区二区| 羞羞漫画18久久大片| 久久躁狠狠躁夜夜爽| 亚洲另类自拍| 国产精品日日做人人爱| 久久婷婷久久| 亚洲午夜国产成人av电影男同| 久久久午夜精品| 夜夜精品视频| 韩国av一区二区三区在线观看 | 欧美色欧美亚洲高清在线视频| 亚洲精品影院| 性伦欧美刺激片在线观看| 亚洲福利视频一区| 欧美性片在线观看| 榴莲视频成人在线观看| 亚洲欧美乱综合| 亚洲国产第一| 久久精品123| 亚洲伊人观看| 91久久国产综合久久蜜月精品| 国产精品久久久久久久久久久久| 久久久久久9| 亚洲女人小视频在线观看| 久久综合九色欧美综合狠狠| 亚洲国产精品久久91精品| 国产精品夜夜夜| 欧美精品久久一区二区| 久久aⅴ国产紧身牛仔裤| 欧美福利一区二区| 香蕉久久夜色精品| 国产精品99久久久久久久久| 国产欧美一区二区三区沐欲 | 久久久久久91香蕉国产| 国产精品99久久久久久白浆小说| 亚洲丰满在线| 在线观看精品视频| 国产精品日韩在线| 欧美日韩综合在线| 欧美激情网友自拍| 欧美 亚欧 日韩视频在线| 久久久蜜臀国产一区二区| 欧美在线日韩在线| 午夜视频精品| 国产精品久久九九| 欧美极品影院| 欧美国产高潮xxxx1819| 你懂的视频一区二区| 欧美成在线观看| 欧美日韩一区二区免费在线观看| 欧美日韩国产首页| 国产精品亚洲成人| 一区二区在线观看av| 亚洲美女毛片| 羞羞色国产精品| 欧美成人精品h版在线观看| 91久久国产自产拍夜夜嗨| 亚洲伦理久久| 香港久久久电影| 欧美成人午夜77777| 国产精品国产三级国产aⅴ9色| 国产精品亚洲综合| 亚洲第一久久影院| 亚洲午夜在线| 久久综合成人精品亚洲另类欧美| 欧美成人小视频| 一区二区三区四区精品| 久久精品人人做人人综合| 欧美国产精品劲爆| 国产欧美日韩视频一区二区三区| 亚洲高清视频一区| 午夜亚洲福利| 亚洲电影免费观看高清完整版在线观看| 日韩视频亚洲视频| 久久免费视频网| 国产精品美女主播| 在线看片成人| 欧美一区二区女人| 亚洲人体1000| 久久亚洲精品视频| 国产日韩专区| 亚洲一区二区成人| 亚洲在线视频一区| 欧美私人啪啪vps| 国产精品一区二区三区久久| 91久久午夜| 久热这里只精品99re8久| 亚洲少妇自拍| 欧美精品在线网站|