BinarySearch on List<T> seems to be returning strange result

Question

I am very new to C#. I have created a List object and then I am performing BinarySearch on a particular item. But the search results seem to strange. Here is the code :

class Element
{
    public int x;
    public Element(int val) { x = val; }
}
class MyContainer : IComparable<MyContainer>
{
    public Element elem;
    public MyContainer(int val) { elem = new Element(val); }
    public MyContainer(Element e) { elem = e; }
    public int CompareTo(MyContainer obj)
    {
        if (elem.x < obj.elem.x) { return -1; }
        else if (elem.x == obj.elem.x) { return 0; }
        else { return 1; }
    }
}
class Program
{
    static void Main(string[] args)
    {
        MyContainer container1 = new MyContainer(100);
        MyContainer container2 = new MyContainer(21);
        MyContainer container3 = new MyContainer(-122);
        Element elemObj = new Element(-122);

        List<MyContainer> list = new List<MyContainer>();
        list.Add(new MyContainer(80));
        list.Add(container1);
        list.Add(container2);
        list.Add(container3);
        list.Add(new MyContainer(90));
        foreach(MyContainer c in list)  Console.WriteLine(c.elem.x);

        if (list.Contains(container3) == true) Console.WriteLine("present");
        else Console.WriteLine("NOT present");
        Console.WriteLine("Search result:::"+list.BinarySearch(new MyContainer(elemObj)));
        Console.WriteLine("Search result:::" + list.BinarySearch(container1));
        Console.WriteLine("Search result:::" + list.BinarySearch(container2));
        Console.WriteLine("Search result:::" + list.BinarySearch(container3));
    }
}

The output is as follows :

80
100
21
-122
90
present
Search result:::-1
Search result:::-6
Search result:::2
Search result:::-1

Why is only the element corresponding to value 21 found and why not the others

Answer 1

Your list isn't sorted to start with. Binary search only works when the original input is sorted. The whole point is that you know that if list[x] = y, then list[a] <= y for all a < x and list[a] >= y for all a > x.

So either you need to sort your list first, or you need to choose a different way of searching (e.g. using a separate hash-based dictionary, or just doing a linear search).

Also note that your CompareTo method can be implemented a lot more simply:

public int CompareTo(MyContainer obj)
{
    return elem.x.CompareTo(obj.elem.x);
}