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

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