2

I have to search a for a name from the array through binary search but, show the corresponding age of the person's name instead. Please no other suggestions, I have to do it with Binary search on 2D arrays.

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;
    }
}

This code is showing the age of everyone 20. The CompareTo() method is not working.

AbdelAziz AbdelLatef
  • 3,650
  • 6
  • 24
  • 52
OddCommand24
  • 371
  • 2
  • 12
  • Why not make a class to hold the name and age, then put them in order in a list and use `List.BinarySearch` with the overload that takes a `IComparer` that you can create to specify to compare on the name only? – juharr Oct 04 '19 at 18:21
  • 2
    Calculating `midpoint2` makes little sense since you’re only searching in one of the values so it should be 0. Your names also aren’t in order so binary search cannot be used. – Sami Kuhmonen Oct 04 '19 at 18:27
  • What you could do is to grab an implementation targeting `IList` from [this](https://stackoverflow.com/questions/967047/how-to-perform-a-binary-search-on-ilistt) question, and then implement an `IList` wrapper for 2D arrays. You only need to implement the property `Count` and the [indexer](https://learn.microsoft.com/en-us/dotnet/csharp/programming-guide/indexers/). All other members of the wrapper could throw a `NotImplementedException` because they are not used be these implementations. – Theodor Zoulias Oct 04 '19 at 18:38

3 Answers3

1

You have 4 major problems in you code:

1- Use midpoint2, lowBound2 and upBound2 for unclear reason, you should use 0 and 1 instead.

2- As you depend on binary search the key elements must be sorted, so "Ana" must be after "Ammara" although she is younger, but you search with name not age, or change it to another name, like "Aca".

3- result should be compared to 0, < 0 and > 0, it has nothing to do with midpoint.

4- You should use Console.WriteLine and break in the first condition only to let the while continue if the name wasn't found yet.

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;
    }
}
AbdelAziz AbdelLatef
  • 3,650
  • 6
  • 24
  • 52
1

There are several problems with your code.

  1. A binary search depends on the data being ordered. Therefore to do a binary search on the names they must be in alphabetical order, however Ammara should come before Ana, not after. However, in this case, you would still be able to successfully search for Zacharaia because it is still after the name at the midpoint.

  2. A problem in the processing code is at the line: x.CompareTo(persons[midpoint, 1]); You want to compare the name in x ("Zacharia") with the name at the midpoint position, however persons[##, 1] is the location of a number. You need to use x.CompareTo(persons[midpoint, 0]);

  3. The CompareTo method returns 0 if the values match, < 0 if the x precedes the value and > 0 if x is after the value. However, you are comparing the result to midpoint which has nothing to do with the relative location of the value. Instead use: if (result == 0) {...} else { if(result > 0) {...} else//The only possibility is for result to be < 0 so you don't need another if here. {...} }

  4. The only time that you have found the value is whe result == 0, however you are writing the answer and breaking out of the while loop for all 3 cases. Only break when you find a match (result ==0).

  5. The name in your array ("Zacharaia") is NOT the same as the name in string x ("Zacharia") therefore you will never find a match.

  6. Ideally, your code should handle never finding a match.

Bill W
  • 1,428
  • 1
  • 20
  • 29
0

If I am not wrong, you want to search names from the Array/List by binary search. For string, you can use Trie data structure to find a name.

If you are asking the names of the person performing search on their age, then proceed with the ages. First, you need to sort the names according to the ages (increasing or decreasing order). Then perform the binary search.

Habibur Rahman
  • 54
  • 8