Как применить бинарный поиск в 2D массивах?

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

Есть несколько проблем с вашим кодом.

1. Бинарный поиск зависит от упорядоченных данных. Поэтому, чтобы выполнить двоичный поиск по именам, они должны быть в алфавитном порядке, однако Аммара должна идти перед Аной, а не после. Однако в этом случае вы все равно сможете успешно выполнить поиск Zacharaia, поскольку он все еще идет после имени в средней точке.

2. Проблема в коде обработки заключается в строке:x.CompareTo (персон [средняя точка, 1]);Вы хотите сравнить имя в x («Захария») с именем в средней точке, однако people [##, 1] - это местоположение числа. Вам необходимо использовать x.CompareTo (people [midpoint, 0]);

3. Метод CompareTo возвращает 0, если значения совпадают, <0, если x предшествует значению, и> 0, если значениях после значения. Однако вы сравниваете результат со средней точкой, которая не имеет ничего общего с относительным расположением значения. Вместо этого используйте: if (result == 0) {...} else {if (result> 0) {...} else // Единственная возможность - результат равен <0, поэтому вам не нужно другое, если здесь,{...}} </p>

4. Единственный раз, когда вы нашли значение, это где результат == 0, однако вы пишете ответ и выходите из цикла while для всех 3случаев. Разрывается только тогда, когда вы найдете совпадение (результат == 0).

5. Имя в вашем массиве ("Zachar a ia") НЕ совпадает симя в строке x («Захария»), поэтому вы никогда не найдете совпадения.

6. В идеале, ваш код должен обрабатывать никогда не находя совпадения.

Answer 2

В вашем коде есть 4 основные проблемы:

1 - используйте midpoint2, lowBound2 и upBound2 по непонятной причине, вместо них следует использовать 0 и 1.

2 - Поскольку вы зависите от бинарного поиска, ключевые элементы должны быть отсортированы, поэтому «Ана» должна быть после «Аммара», хотя она моложе, но вы ищете с именем, а не с возрастом, или измените его на другое имя, например"Aca".

3- result следует сравнивать с 0, < 0 и > 0, это не имеет ничего общего с midpoint.

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 3

Если я не ошибаюсь, вы хотите искать имена из массива / списка с помощью бинарного поиска. Для строки вы можете использовать структуру данных Trie, чтобы найти имя.

Если вы спрашиваете имена человека, выполняющего поиск, по возрасту, то переходите к возрастам. Во-первых, вам нужно отсортировать имена по возрасту (по возрастанию или убыванию). Затем выполните бинарный поиск.