I was proposing a solution to a problem today and realized that I had an invalid assumption about the nature of the Array.BinaySearch function so I ran a quick test to confirm and verify my ignorance. So I defined the following test:
string _mystring = "8,2,3,4,5,6,7,1"; //notice that 1 is not in numerical order string [] myarray = _mystring.Split(','); int result; for (int i=1; i < 9; i++) { result = Array.BinarySearch(myarray, i.ToString()); Console.WriteLine(string.Format("The value of {0} has been found at {1}.",i,result.ToString())); } Console.ReadLine();
This resulted in the following output, clearly it could not find "1" or "8" even though they are at the beginning and the end of the array ... herein my fundamental floor was ultimately expressed and the anomaly revealed.
The simple problem here is that BinarySearch only works on arrays that are sorted! How did I forget that?!?!?
So this serves as an official note to self, when you are using BinarySearch on an unsorted array perform an Array.Sort:
string _mystring = "8,2,3,4,5,6,7,1"; //notice that 1 is not in numerical order string [] myarray = _mystring.Split(','); Array.Sort(myarray);
Doh!
Best case the Sort uses an algorithm with order of n log n, then you have to do the binary search, which I think is order of SQRT(n).
Simply iterating through all the items with a FOR loop is going to user less processing because it is order of N.
Assuming I'm correct on the orders of algorithm, this means to look through a list of 200 items your way would require 200 operations to sort the list, then 10 to do the search for a total of 210.
Simply iterating through the list would require at most 100 operations.
Cheers!
Comments are closed.