开发者

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.Bin开发者_JS百科arySearch(people, s)
            );


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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜