二分查找的實現及注意事項

聽到二分查找，大家可能都會覺得它非常簡單，從而會自然而然地忽略它。那麼在實現這個看似簡單的算法過程中有沒有什麼值得注意的地方呢？
下面是我寫的一個二分查找的實現
int binary_search(int array[],int n,int value)
{
    int begin = 0, end = n-1, mid = 0;
    bool flag =0;    //判斷數據的排序方式，從小到大則為1，從大到小則為0
    for(int i = 0; i < n-1; ++i) //1
    {
        if(array[i] < array[i+1])
        {
            flag = 1;
            break;
        }
        if(array[i] > array[i+1])
        {
            flag = 0;
            break;
        }
    }
   
    if(flag)
    while(begin <= end)    //數據的排序方式，從小到大
    {
        mid = begin/2 + end/2;    //2
        if(array[mid] == value)
            return mid;
        if(array[mid] > value)
            end = mid - 1;        //3注意-1
        else
            begin = mid + 1;    //4注意+1
    }
    else
    while(begin <= end)    //數據的排序方式，從大到小
    {
         mid = begin/2 + end/2;
        if(array[mid] == value)
            return mid;
        if(array[mid] > value)
            begin = mid + 1;   
        else
            end = mid - 1;  
    }
    return -1;
}

在這個程序中，我們需要注意的首先是注釋1中的循環的作用，正如我們所知道的那樣，二分查找要基於已經排好序的數組來實現，那麼這個數組是按什麼順序來排列的呢，從大到小還是從小到大，這個循環的作用就是如此，通常它只會循環1到2次。因為不同的排序方式對查找失敗後，調整縮小搜索范圍的操作是不一樣的，從上面的代碼中也可以看出這點。為了讓這個程序能對這兩種排序方式的數組都適用，這個判斷是必不可少的。

再來看看注釋2的語句，mid為什麼要等於begin/2 + end/2;而不是直接的（begin+end）/2;呢？在數學上這的確沒有什麼不同，但是在計算機裡，卻有很大的不同。設想你的數組很大，為方便說明，我以16位為例子，一個int型整數的最大值為65535，如果你的數組大小為40000，而你要需要查找的數據位於數組的比較後的位置，例如是下標為39800的那個數，那麼在後面的查找中（begin+end）就會超出65535所能表示的范圍，從而mid就會變成一個負數，這樣你就永遠都找不到你要找的數了，還可能發生內存錯誤。

再來看看注釋3和注釋4，很多人在縮小搜索范圍時，都會把加1和減1漏了，這會導致一個什麼的後果呢，就是這個程序可能會陷入死循環，這也是一個常有的錯誤。而為什麼可以加1和減1，因為在查找失敗時，mid肯定不會等於value，所以可以放心地從mid的下一個元素（加1）或mid的前一個元素（減1）開始查找。