使用二進制搜索（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 
} 

這將只在列表中搜索這兩種方式，然後執行您的操作，直至遇到無效字符串，然後這將破壞循環。