CODEWITHSUNDEEP
c#arrayssearch
Razor
Razor

Reputation: 17498

Array.BinarySearch does not find item using IComparable

If a binary search requires an array to be sorted before hand, why does the following code work?

string[] strings = new[] { "z", "a", "y", "e", "v", "u" };
int pos = Array.BinarySearch(strings, "Y", StringComparer.OrdinalIgnoreCase);           
Console.WriteLine(pos);

And why does this code result return -1?

 public class Person : IComparable<Person> {

    public string Name { get; set; }
    public int Age { get; set; }


    public int CompareTo(Person other) {
        return this.Age.CompareTo(other.Age) + this.Name.CompareTo(other.Name);
    }
}
var people = new[] {

                new Person { Age=5,Name="Tom"},
                new Person { Age=1,Name="Tom"},
                new Person { Age=2,Name="Tom"},
                new Person { Age=1,Name="John"},
                new Person { Age=1,Name="Bob"},
            };


            var s = new Person { Age = 1, Name = "Tom" };

            // returns -1
            Console.WriteLine(
                Array.BinarySearch(people, s)
            );

Upvotes: 0

Views: 1348

Answers (1)

Matthew Flaschen
Matthew Flaschen

Reputation: 284796

If you violate the pre-condition ("The elements of array must already be sorted in increasing value according to the sort order defined by comparer; otherwise, the result might be incorrect."), you cause undefined behavior, which sometimes includes, "Hey, it looks like it worked." The same is true with use after free and many other programming errors.

I'm not surprised it works for that input, because "y", and "e" are both equally middle elements. It uses the lower middle, "y", which matches. If you try:

string[] strings = new[] { "z", "a", "y", "e", "e", "v", "u" };

you'll see that doesn't work. Note that there are an odd number of elements. The target is before the middle, while it should be after.

Upvotes: 2

Related Questions