我正在leetcode 上練習問題 704 的二進制搜索。一開始，我只是按照二分查找的概念，想出了這個解決方案：
int search(int* nums, int numsSize, int target){
size_t start=0, end=numsSize-1;
while(start!=end){ // if start == end then break
if(nums[(start end)/2] > target){
end=(start end)/2;
}
else if(nums[(start end)/2] < target){
start=(start end)/2 1;
}
else{
return (start end)/2;
}
}
if(nums[start]==target){ // when start == end
return start;
}
return -1;
}
它的設計不是很好，但它通過了所有測驗用例。
之后，我閱讀了一些關于二進制搜索的文章，我嘗試用這段代碼重新實作它：
int search(int* nums, int numsSize, int target){
size_t start=0, end=numsSize-1;
while(start<=end){
size_t mid = (start end)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid] > target){
end=mid-1;
}
else{
start=mid 1;
}
}
return -1;
}
問題是它只通過 3/47 測驗用例并導致運行時錯誤。
那么是什么讓我的第二個版本導致錯誤，但我的第一個版本沒有。
任何幫助，將不勝感激。
uj5u.com熱心網友回復：
您的第二個實作的唯一問題是使用size_t. 將其更改為int，它應該可以正常作業。
size_t是無符號型別。當搜索正在探測陣列的開頭時，的值end可以是負數。這會在 C 中呼叫未定義的行為。在實踐中，這通常意味著值“下溢”并變成一個巨大的正數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/410340.html
標籤：