BinarySearch在列表中找不到元素：Java

任何人都可以指出我在哪裏出錯了嗎？我用一個調試器遍歷它，它看起來像我的算法應該找到搜索關鍵字，但它不是。（爲了檢查，我打印出'在索引處找到'，然後打印[sorted]列表的內容;我搜索的元素123位於列表中，但返回了'not found'值-1。）BinarySearch在列表中找不到元素：Java

public int binarySearch(ArrayList<Integer> list, int key){ 
    int foundAtIndex = -1; 
    int midPoint = list.size()/2; 
    int midPointValue = list.get(midPoint); 

    if(list.size() > 1){ 
     if(midPointValue == key){ 
      foundAtIndex = midPoint; 
     } 
     else if(midPointValue > key){ 
      ArrayList<Integer> newList = new ArrayList<Integer>(); 
      for(int i = 0; i < midPoint; i++){ 
       newList.add(list.get(i)); 
      } 
      midPoint = midPoint/2; 
      binarySearch(newList, key); 
     } 
     else if(midPointValue < key){ 
      ArrayList<Integer> newList = new ArrayList<Integer>(); 
      for(int j = midPoint+1; j < list.size(); j++){ 
       newList.add(list.get(j)); 
      } 
      midPoint = midPoint/2; 
      binarySearch(newList, key); 
     } 
    } 
    else if(list.size() == 1){ 
     if(list.get(0) == key){ 
      foundAtIndex = 0; 
     } 
    } 

    //return the index where the key was found, or -1 if not found 
    return foundAtIndex; 
}

編輯：好的，所以它發現它了，但我的問題是我需要在原數組返回發現索引。實際上，它縮小了它，然後返回'newList'中元素的索引。所以它會一直以「newList」的形式返回索引。換句話說，我正在尋找返回一個實際的foundAtIndex（在原始數組中的值位於什麼位置），而不是一個布爾值，「was/was not found」值。

來源

2011-05-05 Chris V.

，你是循環建立的子名單，這一事實並沒有那麼大。考慮使用初始數組並傳遞開始和結束參數以及初始列表。 – aepheus 2011-05-05 21:52:00

看到我下面更新的答案。它解決了返回正確索引的問題 – 2011-05-06 22:57:11

每次撥打電話binarySearch(newList, key);時，您將失去退貨結果。您需要設置foundIndex = binarySearch(newList,key)。

另外，因爲您正在依靠list.size()作爲中點 - 您將需要調整您的返回結果（否則它將始終爲-1或0）。

來源

2011-05-05 20:10:37 Assaf

除了使用size（）方法之外，還可以做其他事情嗎？ – 2011-05-05 20:26:43

你可以傳遞一個開始和結束索引到遞歸調用並傳遞整個列表（現在是子列表），這樣它在最後返回的索引將是'全局'索引，而不是子列表中的索引。 – Assaf 2011-05-05 21:04:09

您不存儲遞歸調用的返回值。通過

foundAtIndex = binarySearch(newList, key);

替換兩行

binarySearch(newList, key);

，它應該工作。

來源

2011-05-05 20:11:19

aggghhhh我昨天和我的MergeSort有同樣的問題！我總是忘記存儲值> _ <非常感謝！ :) – 2011-05-05 20:13:20

這是一個解決方案，它返回原始列表中的索引。主要變化是：當您遞歸調用binarySearch時，將其結果添加到newList的偏移量（與list相比）。在midPointValue > key這個偏移量是零，所以沒有什麼可添加的。如果midPointValue < key那麼偏移量是midPoint。

public int binarySearch(ArrayList<Integer> list, int key){ 
    int foundAtIndex = -1; 
    int midPoint = list.size()/2; 
    int midPointValue = list.get(midPoint); 

    if(list.size() > 1){ 
    if(midPointValue == key){ 
     foundAtIndex = midPoint; 
    } 
    else if(midPointValue > key){ 
     ArrayList<Integer> newList = new ArrayList<Integer>(); 
     for(int i = 0; i < midPoint; i++){ 
     newList.add(list.get(i)); 
     } 
     return binarySearch(newList, key); 
    } 
    else if(midPointValue < key){ 
     ArrayList<Integer> newList = new ArrayList<Integer>(); 
     for(int j = midPoint+1; j < list.size(); j++){ 
     newList.add(list.get(j)); 
     } 
     return midPoint + binarySearch(newList, key); 
    } 
    } 
    else if(list.size() == 1){ 
    if(list.get(0) == key){ 
     foundAtIndex = 0; 
    } 
    } 
    //return the index where the key was found, or -1 if not found 
    return foundAtIndex; 
}

其他景點：

沒有必要做下一個遞歸調用之前設置中點。
在方法內部有多個返回是完全合法的。無需將結果一直傳播下去。
point在midPoint和midPointValue是一種多餘的。 Varialbe名稱太長會使代碼更難理解。
最後，無需創建新列表並將原始列表中的元素複製到此新列表中。您可以簡單地通過添加輔助方法來告訴方法僅檢查原始列表的某個部分。

這是我怎麼會寫這個方法：

public int binarySearch(ArrayList<Integer> list, int key) { 
    return binarySearch(list, key, 0, list.size()); 
} 

public int binarySearch(ArrayList<Integer> list, int key, int begin, int end) { 

    if(end <= begin) 
    return -1; // Range is empty => key wasn't found 

    int mid = (begin + end)/2; 
    int midValue = list.get(mid); 

    if(midValue == key) 
    return mid; 
    else if(midValue < key) 
    return binarySearch(list, begin, mid); 
    else 
    return binarySearch(list, mid + 1, end); 
}

來源

2011-05-05 21:40:25

BinarySearch在列表中找不到元素：Java

回答

相關問題