沒有bug的二分查找

二分查找都熟悉吧，先寫一個有bug的二分查找

static int binary(int *arr, int len, int data)
{
    int min = 0;
    int max = len - 1;
    int mid = 0;
    while(min <= max)
    {
        mid = (min + max) / 2;
        if(arr[mid] > data)
            max = mid - 1;
        else if(arr[mid] < data)
            min = mid + 1;
        else
            return mid;
    }
    return -1;
}
           

mid = (min + max) / 2; 這句中 存在一個隐藏的bug，看上去這句話沒問題，當min 和 max很大的時候可能會導緻數組通路出錯  int類型溢出，找的值在數組左端的時候就可能會出現問題。

下邊是修改過後的代碼   mid = min + ((max - min) >> 1);

static int binary1(int *arr, int len, int data)
{
    int min = 0;
    int max = len - 1;
    int mid = 0;
    while(min <= max)
    {
//        mid = min + (max - min) / 2;
        mid = min + ((max - min) >> 1);
        if(arr[mid] > data)
            max = mid - 1;
        else if(arr[mid] < data)
            min = mid + 1;
        else
            return mid;
    }
    return -1;
}