使用二进制搜索（C＃）搜索分类列表

Question

要求是使用二进制搜索方法搜索指定字符串（在下例中为“yz”）的字母排序/排序列表（字符串类型）和返回结果（每个以指定字符串开头的字符串以及该列表中该字符串的索引）在适当的控件（如ListBox）上返回。

问题是BinarySearch方法必须在循环中运行多次，以便返回列表中的所有匹配字符串，而不仅仅是一个。这是我的主要问题。我无法弄清楚如何正确编写这个循环。如果你看看while循环，你会看到我试图删除从列表中找到的结果，所以找不到并返回。这会导致列表中项目索引的问题发生变化。所以它返回结果的错误索引。例如，如果您运行下面的代码，它应该返回索引：9,10,11和12.但是，我得到9,10,9,10，因为当项目被删除时，列表变得更短。我可以用另一个随机字符串替换结果字符串，而不是完全删除它，但这意味着列表不再按字母顺序排序。要使BinarySearch方法起作用，列表务必按字母顺序排序。

BinarySearch方法可能没问题，不需要改变。问题在于循环。我应该提到这是为了在我的大学进行任务，所以我不能使用任何快捷方式代码/内置函数。我已经尝试了几个小时，但无法弄清楚这一点。

public partial class MainWindow : Window 
{ 
    public MainWindow() 
    { 
     InitializeComponent(); 
    } 

    string searchString = "yz"; 

    List<string> list1 = new List<string>(); 

    private void btnSearch_Click(object sender, RoutedEventArgs e) 
    { 
     if (list1.Count != 0) 
     { 
      list1.Clear(); 
     } 

     list1.Add("ant"); //0 
     list1.Add("bb"); //1 
     list1.Add("bc"); //2 
     list1.Add("bD"); //3 
     list1.Add("Be"); //4 
     list1.Add("j");  //5 
     list1.Add("RRR"); //6 
     list1.Add("sT"); //7 
     list1.Add("Uv"); //8  
     list1.Add("yz"); //9 
     list1.Add("yza"); //10 
     list1.Add("yzb"); //11 
     list1.Add("yzc"); //12 

     int index = BinarySearch(list1, 0, list1.Count, searchString); 

     while (index != list1.Count) 
     { 
      listBox1.Items.Add("Index: " + index + " File: " + list1[index]); 

      list1.RemoveAt(index); //Remove from list so we don't find it again 
            // but this changes the index of the list 

      index = BinarySearch(list1, 0, list1.Count, searchString); 
     } 
    } 

    //BinarySearch method to search an alphabetically sorted list for a specified string 
    public int BinarySearch(List<string> strList, int first, int last, string target) 
    { 
     int mid; // index of the midpoint 
     string midStr; // object that is assigned listStr[mid] 
     int origLast = last; 
     // save original value of last 
     while (first < last) 
     // test for nonempty sublist 
     { 
      mid = (first + last)/2; 
      midStr = strList[mid]; 

      int indy = midStr.IndexOf(target, StringComparison.OrdinalIgnoreCase); 

      if (indy == 0) 
       return mid;// have a match, we're only matching the beginning of the string 
      else 
      { 
       int order = string.Compare(target, midStr, StringComparison.OrdinalIgnoreCase); 

       if (order < 0) 
        last = mid; // search lower sublist. Reset last      
       else 
        first = mid + 1; // search upper sublist. Reset first 
      } 
     } 
     return origLast; // target not found 
    } 
} 

Answer 1

你为什么不，一旦你的一个元素的索引，循环起来的指数，直到你到达最后一个对象或对象，这并不从字符串开始，从指数 - 环1直到你达到0或者你到达一个无效的对象。

编辑：要修改你的代码，我会做的是后：

int index = BinarySearch(list1,0,list1.Count,searchString); 

，而不是做你的while循环，消除的对象，我会做：

for (int n=index;n<list1.Count;n++) { 
    if (list1[n].IndexOf(searchString,StringComparison.OrdinalIgnoreCase)!=0) break; 
    listBox1.Items.Add("Index: " + n + " File: " + list1[n]); 
} 
for (int n=index-1;n>=0;n--) { 
    //Do same thing as other loop 
} 

这将只在列表中搜索这两种方式，然后执行您的操作，直至遇到无效字符串，然后这将破坏循环。