使用二進制搜索

Question

問題查找列表項的位置是：

給定的字符串列表，在列表中找到一個特定的字符串，並通過歸併排序字符串的有序列表返回 其索引。有 兩種情況：

1. 的字符串列表，返回它應該是在索引，排序列表。

2. 該字符串不在列表中，返回它應該在有序列表中的索引。

這裏是我的我的代碼，我假設給定的列表已經下令。

對於第二種情況，我如何使用mergesort來查找假定的索引？我會欣賞一些線索。

我正在考慮先獲取原始列表的副本，對其進行排序，並獲取副本列表中字符串的索引。在這裏，我陷入了困境......我是否再次使用mergesort來獲取複製列表中不存在的字符串的索引？

public static int BSearch(List<String> s, String a) { 

    int size = s.size(); 
    int half = size/2; 
    int index = 0; 
    // base case? 

    if (half == 0) { 

     if (s.get(half) == a) { 
      return index; 
     } else { 
      return index + 1; 
     } 
    } 

    // with String a 
    if (s.contains(a)) { 
     // on the right 
     if (s.indexOf(s) > half) { 
      List<String> rightHalf = s.subList(half + 1, size); 
      index += half; 
      return BSearch(rightHalf, a); 

     } else { 
      // one the left 
      List<String> leftHalf = s.subList(0, half - 1); 
      index += half; 
      return BSearch(leftHalf, a); 
     } 
    } 
    return index; 

}

當我運行這段代碼，該指數不更新。我不知道這裏有什麼問題。當我使用列表中的字符串測試代碼時，我只得到0或1。

Answer 1

您的代碼只返回0或1，因爲您不會每次遞歸調用都跟蹤索引，而不是每次重置爲0。此外，要找到不存在的元素應該在哪裏，請考慮列表{0,2,3,5,6}。如果我們要在這裏運行二分法搜索以查找4，則應該停止在元素5所在的索引處。希望這足以讓你開始！