用二进制搜索填充列表

问题描述：

我列出了填充文件名。我需要用搜索结果填充另一个列表。这个搜索结果必须通过二进制搜索来完成，下一个规范：关键字可以匹配文件名或它的子串（0，key.Length）。例如关键字= “车” 搜索结果= “car.gif”， “carffur.pdf” 等，但不是 “mobilecar.jar”用二进制搜索填充列表

我的二进制搜索：

class Search 
{ 
    private const int KEY_NOT_FOUND = -1; 

    public static int BinarySearch<T>(List<T> A, T key, IComparer<T> comparer, int imin, int imax) 
    { 
     // test if array is empty 
     if (imax < imin) 
      // set is empty, so return value showing not found 
      return KEY_NOT_FOUND; 
     else 
     { 
      // calculate midpoint to cut set in half 
      int imid = imin + ((imax - imin)/2); 
      int compareResult = comparer.Compare(A[imid], key); 
      // three-way comparison 
      if (compareResult > 0) 
       // key is in lower subset 
       return BinarySearch<T>(A, key, comparer,imin, imid - 1); 
      else if (compareResult < 0) 
       // key is in upper subset 
       return BinarySearch<T>(A, key, comparer, imid + 1, imax); 
      else 
       // key has been found 
       return imid; 
     } 
    } 
}

我的比较器类：

class SubStringComparison : IComparer<string> 
{ 
    public int Compare(string x, string y) 
    { 
     if (x.Length > y.Length && x.Substring(0, y.Length).Equals(y)) 
      return 0; 

     return String.Compare(x, y, StringComparison.OrdinalIgnoreCase); 
    } 
}

用法：

private void backgroundWorkerSearch_DoWork(object sender, DoWorkEventArgs e) 
    { 
     SearchForFiles(); 
    } 

    private void SearchForFiles() 
    { 
     List<string> files = listBoxFiles.Items.OfType<string>().ToList(); 
     searchResults = new List<string>(); 
     listBoxFiles.Dispatcher.Invoke(new Action(delegate() 
      { 
       while (true) 
       { 
        int index = Search.BinarySearch<string>(files, textBoxFileToSearch.Text, new SubStringComparison(), 0, files.Count - 1); 
        if (index == -1) 
         break; 
        else 
         searchResults.Add(files[index]); 
       } 
      })); 
    }

请出示的努力和解释什么是“搜索结果必须由二进制搜索来完成”。通常这是通过'fileNames.OrderBy（....）完成的，但是你的要求很不明确。 – 2013-03-16 05:58:07

我不应该使用任何内置的.net方法。我必须自己写。问题是，当我使用自己写的二进制搜索时，它每次都会返回一个结果，但我需要它返回另一个结果。 – 2013-03-16 06:00:57

你在看什么 - 这样做的权限？请说清楚你的问题是“自己写”，这样可以提供帮助。 – 2013-03-16 06:05:37

答

-1，作业的一部分，你有麻烦？它是二进制搜索吗？是否选择文件名？ BackgroundWorker是不是按预期工作？

我看到你有一些BackgroundWorker的问题，好像你在BackgroundWorker线程中从UI中选择了一个文件列表，然后创建一个将在主线程中运行的Action，这是一种非常奇怪的方式做到这一点。

正确的方法是：

public void button1_Click(object sender) 
{ 
    List<string> files = listBoxFiles.Items.OfType<string>().ToList(); 
    string key = textBoxFileToSearch.Text; 
    backgroundWorkerSearch.RunWorkerAsync(new Tupple<List<string>,string>(files, key)); 
} 

void backgroundWorkerSearch_DoWork(object sender, DoWorkEventArgs e) 
{ 
    var state = e.Argument as Tupple<List<string>,string>; 
    List<string> files = state.Item1; 
    string key = state.Item2; 
    // You can now access the needed data. 
    List<string> searchResult = new List<string>(); 
    // ... 
    e.Result = searchResult; 
} 

void backgroundWorkerSearch_RunWorkerCompleted(RunWorkerCompletedEventArgs e) 
{ 
    List<string> searchResult = e.Result; 
    // Show result in the UI thread. 
}

用二进制搜索填充列表

相关推荐