首頁猿問二分查找多次返回錯誤答案

二分查找多次返回錯誤答案

Java

慕碼人2483693 2023-12-10 15:03:15

我已經實現了迭代二分搜索算法，該算法返回找到的元素的索引（如果該元素不在數組中，則返回-1）：public static int binarySearch(int[] array, int target) { int left = 0; int right = array.length - 1; while (left <= right) { int mid = (left + right) / 2; if (array[mid] == target) { return mid; } else if (array[mid] < target) { right = mid - 1; } else { left = mid + 1; } } return -1;}當我嘗試在不在數組中的元素上測試它時，它返回正確的答案，當我用數組嘗試它時：{1,5,23,111}并且目標是數字 5，它返回正確的結果，在本例中為 1，但是當我嘗試使用相同的數組，但它返回的數字 111 -1，我也嘗試過使用不同的數組和多個目標數字，很多次它返回 -1，即使該數字存在于數組中，任何幫助說明為什么會這樣發生？

查看完整描述

4 回答

蕭十郎

TA貢獻1815條經驗獲得超13個贊

您的左/右前進是向后的。當當前位置的元素mid小于目標時，則需要搜索右半部分，當當前mid位置的元素大于目標（else塊）時，則需要搜索左半部分。

您發現正確的唯一原因5是mid在第一次迭代中碰巧是正確的。

else if切換和塊中的語句else。

else if (array[mid] < target) { left = mid + 1; }

else { right = mid - 1; }

或者反轉條件的比較意義else if。

else if (array[mid] > target) { right = mid - 1; }

else { left = mid + 1; }

反對回復 2023-12-10

慕哥9229398

TA貢獻1877條經驗獲得超6個贊

您的程序存在一些邏輯問題。

第一個問題是使用else包含語句if的條件return。由于該方法會return在if條件為時執行true，因此添加 anelse是沒有用的。需要使用來else選擇兩個選項中的一個（即不是兩者都選擇）。使用return帶有第一個選項的語句后，您已經禁止第二個選項。
right第二個問題是和變量的計算放錯了位置left。邏輯應該是：target如果大于處的數字，則忽略左半部分mid，為此，只需left在之外前進一位即可mid；否則（即，如果target大于less處的數字），通過向后mid移動一個位置來忽略右半部分。right

工作方案如下：

public class BinarySearchDemo {

public static void main(String[] args) {

int arr[] = { 1, 5, 23, 111 };

System.out.println(binarySearch(arr, 23));

System.out.println(binarySearch(arr, 20));

}

public static int binarySearch(int[] array, int target) {

int left = 0;

int right = array.length - 1;

while (left <= right) {

int mid = left + (right - 1) / 2;

if (array[mid] == target) {

return mid;

}

if (array[mid] < target) {

left = mid + 1;

} else {

right = mid - 1;

}

return -1;

}

輸出：

-1

反對回復 2023-12-10

www說

TA貢獻1775條經驗獲得超8個贊

問題是當你更新left和right. 您正在錯誤的 if 語句中更新它們。

當時array[mid] < target，您想要更新left指針并在右側子數組中搜索，反之亦然。

所以你的更新應該是這樣的：

else if (array[mid] < target) { left = mid + 1; }

else { right = mid - 1; }

反對回復 2023-12-10

GCT1015

TA貢獻1827條經驗獲得超4個贊

想添加評論，但還不能評論

使用正確的邏輯修復代碼后（如上面的答案），這里有一些需要改進的代碼：
不要這樣做：int mid=(left+right)/2;
這樣做：int mid = low + ((high - low) / 2);或這個int mid = (low + high) >>> 1;

反對回復 2023-12-10

4 回答
0 關注
246 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

二分查找多次返回錯誤答案

二分查找多次返回錯誤答案

4 回答

添加回答