那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,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 那谁 阅读(18243) 评论(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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理