首頁(yè) 猿問(wèn) 二分查找多次返回錯(cuò)誤答案

二分查找多次返回錯(cuò)誤答案

Java

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

我已經(jīng)實(shí)現(xiàn)了迭代二分搜索算法，該算法返回找到的元素的索引（如果該元素不在數(shù)組中，則返回-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;}當(dāng)我嘗試在不在數(shù)組中的元素上測(cè)試它時(shí)，它返回正確的答案，當(dāng)我用數(shù)組嘗試它時(shí)：{1,5,23,111}并且目標(biāo)是數(shù)字 5，它返回正確的結(jié)果，在本例中為 1，但是當(dāng)我嘗試使用相同的數(shù)組，但它返回的數(shù)字 111 -1，我也嘗試過(guò)使用不同的數(shù)組和多個(gè)目標(biāo)數(shù)字，很多次它返回 -1，即使該數(shù)字存在于數(shù)組中，任何幫助說(shuō)明為什么會(huì)這樣發(fā)生？

查看完整描述

4 回答

蕭十郎

TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超13個(gè)贊

您的左/右前進(jìn)是向后的。當(dāng)當(dāng)前位置的元素mid小于目標(biāo)時(shí)，則需要搜索右半部分，當(dāng)當(dāng)前mid位置的元素大于目標(biāo)（else塊）時(shí)，則需要搜索左半部分。

您發(fā)現(xiàn)正確的唯一原因5是mid在第一次迭代中碰巧是正確的。

else if切換和塊中的語(yǔ)句else。

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

else { right = mid - 1; }

或者反轉(zhuǎn)條件的比較意義else if。

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

else { left = mid + 1; }

反對(duì) 回復(fù) 2023-12-10

慕哥9229398

TA貢獻(xiàn)1877條經(jīng)驗(yàn) 獲得超6個(gè)贊

您的程序存在一些邏輯問(wèn)題。

第一個(gè)問(wèn)題是使用else包含語(yǔ)句if的條件return。由于該方法會(huì)return在if條件為時(shí)執(zhí)行true，因此添加 anelse是沒(méi)有用的。需要使用來(lái)else選擇兩個(gè)選項(xiàng)中的一個(gè)（即不是兩者都選擇）。使用return帶有第一個(gè)選項(xiàng)的語(yǔ)句后，您已經(jīng)禁止第二個(gè)選項(xiàng)。
right第二個(gè)問(wèn)題是和變量的計(jì)算放錯(cuò)了位置left。邏輯應(yīng)該是：target如果大于處的數(shù)字，則忽略左半部分mid，為此，只需left在之外前進(jìn)一位即可mid；否則（即，如果target大于less處的數(shù)字），通過(guò)向后mid移動(dòng)一個(gè)位置來(lái)忽略右半部分。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;

}

輸出：

2

-1

反對(duì) 回復(fù) 2023-12-10

www說(shuō)

TA貢獻(xiàn)1775條經(jīng)驗(yàn) 獲得超8個(gè)贊

問(wèn)題是當(dāng)你更新left和right. 您正在錯(cuò)誤的 if 語(yǔ)句中更新它們。

當(dāng) 時(shí)array[mid] < target，您想要更新left指針并在右側(cè)子數(shù)組中搜索，反之亦然。

所以你的更新應(yīng)該是這樣的：

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

else { right = mid - 1; }

反對(duì) 回復(fù) 2023-12-10

GCT1015

TA貢獻(xiàn)1827條經(jīng)驗(yàn) 獲得超4個(gè)贊

想添加評(píng)論，但還不能評(píng)論

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

反對(duì) 回復(fù) 2023-12-10