Re: ArrayList BinarySearch vs Contains

Hi Tom,

"Big O Notation"
http://en.wikipedia.org/wiki/Big_o_notation

Basically you can think of it as the "n"umber of "O"perations that is the
worst-case scenario to find the specified item in the list.

e.g., if you have 10 items in the list then the worst case in a linear search
would be O(n). This means that the worst case scenario would be examining
every item in the list (10 operations). The worst-case in a binary search
would be O(lg(n)). Binary logarithm of 10 operations. Binary log is the
worst case scenario because a binary search cuts the list in half, then
performs the same operation again on the half that contains the search item.
The pattern is continued until only one or zero items remain. If the list
isn't sorted properly than the search may fail because the algorithm might
chose the "wrong" half in which to continue searching after comparing the
current item to the search item.

"Binary Logarithm"
http://en.wikipedia.org/wiki/Binary_logarithm

"Binary Search"
http://en.wikipedia.org/wiki/Binary_search

--
Dave Sexton

"tshad" <tscheiderich@xxxxxxxxxxxxxxx> wrote in message
news:eFmOqESBHHA.2276@xxxxxxxxxxxxxxxxxxxxxxx
"Carl Daniel [VC++ MVP]" <cpdaniel_remove_this_and_nospam@xxxxxxxxxxxxxxx>
wrote in message news:O9R3DARBHHA.4740@xxxxxxxxxxxxxxxxxxxxxxx
"tshad" <tscheiderich@xxxxxxxxxxxxxxx> wrote in message
news:u8iJyqQBHHA.4256@xxxxxxxxxxxxxxxxxxxxxxx
Which is better to use with an ArrayList: BinarySearch or Contains?

The list is only going to have strings in it and it will be sorted.

Then BinarySearch is better. Contains will be an O(n) operation always
(since it doesn't know whether the data is sorted), while BinarySearch is
an O(lg(n)) operation. Just make sure that the data really is sorted!

What does O(n) and O(lg(n)) mean?

Thanks,

Tom



.

Loading