Binary Search with List in c#

Question

I am using c# WPF for developing a Windows Application. The application requires a class as follows

public class Limits
{

    public String col1
    {
        get;
        set;
    }


    public String col2
    {
        get;
        set;
    }

    public String col3
    {
        get;
        set;
    }
}

I am using a List to Store Objects like:-

List myList<Limits> = new List<Limits>();

"myList" has around 15000 Objects.

Now, I want to search this myList for a particular attribute. Eg: I want to find out the object that has col1 set as "abc".

How can I use Binary Search for this problem?

Using binary search needs the list to be sorted already. Is it? If not, why not use LINQ? — Dmitry Sadakov, Aug 07 '15 at 23:51
@ChrisKnight Linq would have the time compexity `O(n)` where binary search `O(log(n))` — Eser, Aug 07 '15 at 23:59
@Eser, but binary search requires the list to be sorted. And it will be sorted according to either col1, col2 or col3, but not all of them... — Thomas Levesque, Aug 08 '15 at 00:34

Guffa · Accepted Answer · 2015-08-08T00:05:11.797

5

First of all, the list has to be sorted on the col1 property for you to be able to use binary search at all.

You would need a comparer that compares the col1 property:

public class LimitsComparer : IComparer<Limits> {

  public int Compare(Limits x, Limits y) {
    return x.col1.CompareTo(y.col1);
  }

}

Then you can use that to do the binary search:

int index = myList.BinarySearch(new Limits { col1 = "abc" }, new LimitsComparer());

The index returned is:

The zero-based index of item in the sorted List, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.

You can also use the Where method to get the objects that has that property:

List<Limits> result = myList.Where(x => x.col1 == "abc").ToList();

Although that is not quite as efficient, you should still consider if that is a better solution as it's easier to implement and gives a result that is easier to handle. Also (and this might be more important), it works even if the list isn't sorted on col1.

edited Aug 08 '15 at 00:05

answered Aug 07 '15 at 23:59

Guffa

687,336
108
737
1,005

1

The list has to be sorted before you call `BinarySearch`: *The `List` must already be sorted according to the comparer implementation; otherwise, the result is incorrect.* – MarcinJuraszek Aug 08 '15 at 00:06
1

@MarcinJuraszek: Yes, that's why I stated that in the very first paragraph of the answer. – Guffa Aug 08 '15 at 00:14
Sorry, it wasn't clear to me. I can imagine a `BinarySearch` method that does the sorting inline, especially when provided with comparer. It might be just me though. – MarcinJuraszek Aug 08 '15 at 00:16
4

@MarcinJuraszek: That would defeat the purpose of a binary search, as it would make it less efficient than a linear search. – Guffa Aug 08 '15 at 00:18

score 2 · Answer 2 · answered Aug 07 '15 at 23:53

2

You could use somthing like this.

myList.Where(i => i.col1 == "abc").ToList();

answered Aug 07 '15 at 23:53

Juan M. Elosegui

6,471
5
35
48

score 1 · Answer 3 · answered Aug 08 '15 at 00:59

Use a dictionary where the keys are stored in a hash table. Linq will create the cdictionary easily.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication41
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Limits> myList = new List<Limits>();

            //dictionary with unique keys
            Dictionary<string, Limits> dict1 = myList.AsEnumerable()
                .GroupBy(x => x.col2, y => y)
                .ToDictionary(x => x.Key, y => y.FirstOrDefault());

            //dictionary with keys having multiple values
            Dictionary<string, List<Limits>> dict2 = myList.AsEnumerable()
                .GroupBy(x => x.col2, y => y)
                .ToDictionary(x => x.Key, y => y.ToList());

            Limits abc = dict1["abc"];

        }
    }
    public class Limits
    {
        public String col1 { get; set; }
        public String col2 { get; set; }
        public String col3 { get; set; }
    }
}

score 0 · Answer 4 · edited May 23 '17 at 12:14

0

unless you explicitly want to use binary search, you should use the standard Linq functions available to you. Unless your list is already sorted, this might be more efficient than binary sort.

  var myList = new List<Limits> {....}
  var entry = myList.Where(l => l.col1== "abc").FirstOrDefault();
  if(entry == null)
  { // no match found }

If you really want binary search, ref Can LINQ use binary search when the collection is ordered?

edited May 23 '17 at 12:14

Community

1
1

answered Aug 08 '15 at 00:26

KnightFox

3,132
4
20
35

that will throw an InvalidOperationException if the input sequence contains more than one element. – Juan M. Elosegui Aug 08 '15 at 00:31
You can use FirstOrDefault if your list contains duplicates or SingleOrDefault with no duplicates – KnightFox Aug 08 '15 at 00:31

Binary Search with List in c#

4 Answers4