實現二進制搜索

這是我的二進制搜索：實現二進制搜索

int binarySearch(int arr[], int value, int min, int max){ 
    int pos = -1; 

    while (max >= min && pos == -1) { 
    int mid = (max+min)/2; 

    if(arr[mid] == value){ 
     pos = mid; 
    }else if(arr[mid] < value){ 
     min = mid +1; 
    }else if(arr[mid] > value){ 
     max = mid -1; 
    } 

    } 
    return pos; 
}

我這樣調用它：

//Arr contain values 0-63 
int i = binarySearch(arr, 64, 0, 64);

這些都是值中旬

32 48 56 60 62 63 64

在最後一次檢查我當陣列中的最後一個位置是63時，嘗試訪問位置爲64的元素。

我的實現有什麼問題？

來源

2012-10-28 Carlj901

我建議逐行檢查「max」，「min」和「mid」的值，在調試器中逐行執行代碼。還要確保數組實際上已排序。 –

代碼可以在代碼塊上正常運行。確保陣列已排序幷包含正好64個元素 –

-1用於在聊天中轉儲鏈接。 – Puppy

您的陣列包含0值-63（正如你所提到的），你給出了以下最小值和最大值：min = 0，max = 64。並更改以下行，以便您的代碼可以處理高int值，否則存在內存溢出的可能性。

 int mid = min+(max-min)/2;

上述公式簡化爲（最大值+最小值）/ 2本身，而是保護整數溢出。

來源

2012-10-28 19:49:49 Gaurav

它不必要。嘗試使用這兩個版本運行。 –

@CodingMash：好吧，如果你的索引是巨大的，這將是有意義的。但是你幾乎不能在實踐中分配一個數組。 – Groo

當max == min時，你的長度是0，所以你不應該進入循環。變化，而條件(max > min && ...)，如果你的高水是「一個過去的結束」（和你的高水可能應該是「一個過去的結束」，這是一個非常有用的模式）

噢，並使其max = mid代替max = mid-1，因爲max代表「一個超越終點」而不是最後一個元素。

作爲一般的編碼風格改進，當做這種類型的代碼時，折騰會在索引處於邊界內的地方聲明。這不僅可以發現問題早，它也可以幫助你的理由什麼值是界限，哪些不是？

來源

2012-10-28 19:17:11 Yakk

如果我做max> min，我將永遠無法在數組中的位置0找到任何東西。 – Carlj901

當'max = 1'和'min = 0'時，'mid'是什麼？你的代碼有兩個問題，都涉及'max'的含義。我建議你說要搜索的索引是{'min'，'min + 1'，'min + 2'，...，'max-2'，'max-1'}：'max '是「通過最後一個搜索索引」。這與以'max'開頭的'64'一致。但是，爲了解決這個問題，當你發現'mid'的值太大時，搜索範圍應該是['min'，'mid'）而不是['min'，'mid-1'）。（我使用[a，b）表示a和b之間的半開區間，其中不包括b） – Yakk

嘗試

while (max > min && pos == -1) { 
int mid = (max+min)/2; 

if(arr[mid] == value){ 
    pos = mid; 
}else if(arr[mid] < value){ 
    min = mid; 
}else if(arr[mid] > value){ 
    max = mid; 
}

}

來源

2012-10-28 19:25:48 user1061392

只有代碼答案不適用於SO。 –

然後我無法訪問第一個元素。 – Carlj901

實現二進制搜索

回答

相關問題