-2

我想问一下如何在有 50,000 个结构的 List 中实现二进制搜索。

我按单词对这个列表进行排序，例如listSub.OrderBy(s => s.word); 

public struct SubItem
{
    public string word;
    public int count;

    public SubItem(string word, int count)
    {
        this.word = word;
        this.count = count;
    }
}

我不知道如何在List < SubItem > 中进行二进制搜索。你能帮助我吗？

4

2 回答 2

0

二分查找的关键是中心项左侧的所有项都小于中心项，而右侧的所有项都大于中心项。另一个关键是列表的任何给定部分本身都表现为排序列表，因此该属性仍然适用。所以你不断地把列表分成两半，直到你找到你的元素。这通常通过递归来完成，以空列表作为元素不存在于列表中的基本情况。

这里有一些伪代码可以帮助您入门：

find (list, start, end, target) {
     if (start > end)  // this is called a base case, look into recursion
        return -1

     center = (end - start) / 2

     if list[center] == target    // this is also a base case
          return center;

     else if list[center] > target
          return find(list, start, center-1, target)

     else 
          return find(list, center+1, end, target)

}

我们会像这样运行它：

list = [ 1 , 3, 7, 9, 12, 15, 17, 21, 28 ]
// need to find the target in the list
find(list, 0, list.length - 1, 3);

这将首先查看 12，它比我们的目标大，然后它将列表分成两半，查看较小一半的中间 3 并找到它，并返回它的索引。它在越来越大的列表上往往更有益。

我说它使用递归，这意味着两件事：它会调用自己，直到找到答案，当它找到答案时，它会停止调用自己。您稍后可能会发现两种主要的递归，但最重要的部分是这两个：递归步骤（调用自身）和基本情况（当它停止调用自身时）。没有这两个部分，某些东西就不是递归的。

于 2013-04-13T19:01:00.333 回答
0

使用数组列表。它有一个名为 BinarySearch 的方法。

于 2016-06-19T16:06:12.027 回答