Re: ArrayList BinarySearch vs Contains

"Dave Sexton" <dave@jwa[remove.this]online.com> wrote in message
news:%23QBKHbSBHHA.1196@xxxxxxxxxxxxxxxxxxxxxxx
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)).

Note:

"Order" stated by itself is almost always for *average* performance, not
worst-case. One would normally specify explicitly if describing the
worst-case order for an algorithm.

For example, it is NOT true that "the worst-case in a binary search would be
O(log(n))" for all implementations of a binary search. If you have a sorted
array, it's true that the worst case is O(log(n)). However, if you have a
binary tree, a search on that tree could be as bad as O(n).

Pete


.

Relevant Pages

  • Re: Fortran to find nearest point from set in 3-D
    ... binary search. ... you need an extension of a binary tree to 3-D. ... as well as the algorithms above). ... you'll find a pile of technical papers describing various ...
    (sci.math.num-analysis)
  • Re: Search a list/array of objects for specified criteria?
    ... even where the distribution is uneven. ... we are not talking about a binary tree. ... We are talking about using a binary search algorithm over a sorted list. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: ArrayList BinarySearch vs Contains
    ... thought O notation always represented worst-case, so thanks for correcting me. ... it is NOT true that "the worst-case in a binary search would be ... binary tree, a search on that tree could be as bad as O. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: No trees in the stdlib?
    ... sorted list using binary search. ... With Oinsertions and removals, ... A decent self-balancing ... binary tree will generally do those in O. ...
    (comp.lang.python)