我正在做一個作業。我必須創建一個在數組中搜索特定 int 的方法。假設數組已經按從最低數到最高數排序。但條件是它必須通過將所述數組切成兩半并檢查目標數字位于哪一半來進行搜索，然后再次將所述一半切成兩半，依此類推。我們也被要求不要使用遞歸方法。這是我想出的代碼，但我沒有看到我的錯誤，任何幫助更好地理解問題的幫助都非常感激！public static boolean SearchInHalf(int[] array, int targetint){ int fin = array[array.length-1]; int init = array[0]; int range = fin-init; if ( targetint>array[array.length-1] || targetint< array[0]) { return false; } while (range>=2) { int half = array[range/2]; if (targetint>half) { init = half; range = fin-init; half = array[range/2]; } else if (targetint<half) { fin = half; range = fin-init; half = array[range/2]; } else if (targetint==half || targetint==fin || targetint==init) { return true; } } return false;}
2 回答
米脂
TA貢獻1836條經驗 獲得超3個贊
您的問題稱為“二分搜索”。為了使二分搜索工作，數組中的元素必須已經排序（這是您的情況，讓我們假設升序）。二分查找首先將鍵與數組中間的元素進行比較：
如果key小于中間元素，則只需要在數組的前半部分繼續查找key。
如果key大于中間元素，則只需要在數組的后半部分繼續查找key。
如果鍵等于中間元素，則搜索以匹配結束。
所以二分查找法每次比較后至少消除數組的一半。假設您將在靜態主函數中調用此方法：
public static int binarySearch(int[] list, int key) {
int low = 0;
int high = list.length - 1;
while(high >= low) { //search array until there is a single element left
int mid = (low + high) / 2; //mark middle index
if (key < list[mid]) //if key is smaller than the middle element..
high = mid - 1; //new high is the middle element
else if (key == list[mid]) //if key=middle element --> voila!
return mid; //returns the index of searched element if it is in your array
else
low = mid + 1; //if key is greater than the middle element new low is middle element
}
return –low - 1; //high < low, key not found
}
偶然的你
TA貢獻1841條經驗 獲得超3個贊
像這樣解決了：
while (true) {
if (targetint>array[array.length-1] || targetint<array[0])
return false;
int middleInt = array[Math.round(array.length/2)];
if (middleInt == targetint) {
return true;
} else if (targetint<middleInt) {
int[] firstHalf = new int[array.length/2];
System.arraycopy(array, 0, firstHalf, 0, firstHalf.length);
array = firstHalf;
} else if (targetint>middleInt) {
int[] secondHalf = new int[array.length/2];
System.arraycopy(array, array.length/2, secondHalf, 0, secondHalf.length);
array = secondHalf;
} else if(array.length == 1)
return false;
}
添加回答
舉報
0/150
提交
取消