使用二进制搜索

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所在的索引处。希望这足以让你开始！