如何在二维数组中应用二进制搜索？

Question

我必须通过二进制搜索从数组中搜索姓名，但显示的是此人姓名的相应年龄。请不要提出其他建议，我必须在二维数组上进行二进制搜索。

string[,] persons = new string[4, 2];
persons[0, 0] = "Ana";
persons[0, 1] = "19";
persons[1, 0] = "Ammara";
persons[1, 1] = "20";
persons[2, 0] = "Marilyn";
persons[2, 1] = "40";
persons[3, 0] = "Zacharaia";
persons[3, 1] = "70";
string x = "Zacharia";
int upBound = persons.GetLength(0) - 1;
int lowBound = 0;
while (lowBound <= upBound)
{
    int midpoint = lowBound + (upBound - lowBound) / 2;
    int result = x.CompareTo(persons[midpoint, 1]);
    if (result == midpoint)
    {
        Console.WriteLine("The value is present at:" + persons[midpoint, 1]);
        break;
    }
    else if (result > midpoint)
    {
        lowBound = midpoint + 1;
        Console.WriteLine("The value is present at:" + persons[lowBound, 1]);
        break;
    }
    else if (result < midpoint)
    {
        upBound = midpoint - 1;
        Console.WriteLine("The value is present at:" + persons[upBound, 1]);
        break;
    }
}

此代码显示每个人的年龄为 20。CompareTo() 方法无效。

Answer 1

你的代码有4个主要问题：

1- 使用midpoint2、lowBound2和upBound2，原因不明，应使用0和1。

2- 因为你依赖二分查找，所以关键元素必须排序，所以 "Ana" 必须在 "Ammara" 之后，虽然她更年轻，但你用名字而不是年龄搜索，或者改变它换个名字，比如 "Aca".

3-result应该比作0、< 0和> 0，与midpoint、[=24=没有关系]

4- 您应该在第一个条件中使用 Console.WriteLine 和 break，以便在尚未找到名称时让 while 继续。

string[,] persons = new string[4, 2];
persons[0, 0] = "Aca";
persons[0, 1] = "19";
persons[1, 0] = "Ammara";
persons[1, 1] = "20";
persons[2, 0] = "Marilyn";
persons[2, 1] = "40";
persons[3, 0] = "Zach";
persons[3, 1] = "70";
string x = "Aca";
int upBound = persons.GetLength(0) - 1;
int lowBound = 0;
while (lowBound <= upBound)
{
    int midpoint = lowBound + (upBound - lowBound) / 2;
    int result = x.CompareTo(persons[midpoint, 0]);
    if (result == 0)
    {
        Console.WriteLine("The value is present at:" + persons[midpoint, 1]);
        break;
    }
    else if (result > 0)
    {
        lowBound = midpoint + 1;
    }
    else
    {
        upBound = midpoint - 1;
    }
}

Answer 2

如果我没记错的话，你想通过二进制搜索从 Array/List 中搜索名称。对于string，可以使用Trie数据结构来找名字。

如果您要询问执行年龄搜索的人的姓名，请继续搜索年龄。首先，您需要根据年龄对姓名进行排序（升序或降序）。然后进行二分查找。

Answer 3

您的代码有几个问题。

二进制搜索取决于所排序的数据。因此，要对名称进行二进制搜索，它们必须按字母顺序排列，但是 Ammara 应该排在 Ana 之前，而不是之后。但是，在这种情况下，您仍然可以成功搜索到 Zacharaia，因为它仍然位于中点名称之后。
处理代码中的问题在以下行： x.CompareTo(人[中点, 1]); 您想将 x ("Zacharia") 中的名称与中点位置的名称进行比较，但是 persons[##, 1] 是数字的位置。你需要使用 x.CompareTo(人[中点, 0]);
CompareTo 方法 returns 如果值匹配则为 0，如果 x 在值之前则为 < 0，如果 x 在值之后则为 > 0。但是，您将结果与中点进行比较，这与值的相对位置无关。而是使用：如果（结果 == 0） {...} 别的 { 如果（结果 > 0） {...} else//唯一的可能是 result < 0 所以你不需要另一个 if 在这里。 {...} }
您唯一一次找到该值是当结果 == 0 时，但是您正在为所有 3 种情况编写答案并跳出 while 循环。仅在找到匹配项时中断（结果 ==0）。
数组中的名称 ("Zacharaia") 与字符串 x 中的名称 ("Zacharia") 不同，因此您永远找不到匹配项。
理想情况下，您的代码应该处理永远找不到匹配项的问题。

如何在二维数组中应用二进制搜索？

How to apply binary search in 2D Arrays?

c#

arrays

binary

search

2d