二分查找算法(迭代和递归版本)[VC/C++编程]

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