二分查找算法(迭代和递归版本)

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[]　=　{0,1,2,3,4,5,6,7,13,19};

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

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

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

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

　　　　return　0;
}

• 没有相关文章