Thread: no. of comparisons in linear/binary search

  1. #1
    Registered User alice's Avatar
    Join Date
    Mar 2004
    Posts
    36

    no. of comparisons in linear/binary search

    hi, what is the no. of comparison in a worst case unsorted one-dimensional array of size N with linear search?

    is it 'N'?

    and if worst case sorted one-dimensional array of size N with binary search,

    is it (log N / log2) ?

    but what is best case in binary search?

  2. #2
    Registered User CompiledMonkey's Avatar
    Join Date
    Feb 2002
    Location
    Richmond, VA
    Posts
    438
    Quote Originally Posted by alice
    hi, what is the no. of comparison in a worst case unsorted one-dimensional array of size N with linear search?

    is it 'N'?

    and if worst case sorted one-dimensional array of size N with binary search,

    is it (log N / log2) ?

    but what is best case in binary search?
    I dunno if I'm right, but I'll try.

    worst case for linear search: n
    worst case binary search: log n
    best case binary search: 1 (assuming it found the result on the first attempt)

  3. #3
    Im a Capricorn vsriharsha's Avatar
    Join Date
    Feb 2002
    Posts
    192
    Well, just to add a small element....
    You refer to the order by the Big O notation.
    Order for Linear Search is: O(n)
    and order for Binary Search is: O(log n).

    Cheers,
    Harsha.
    Help everyone you can

  4. #4
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Worse case is log n / log 2 rounded up to the next whole integer.

    So: 8,000,000 elements would require at most 23 searches.

  5. #5
    Registered User CompiledMonkey's Avatar
    Join Date
    Feb 2002
    Location
    Richmond, VA
    Posts
    438
    Quote Originally Posted by vsriharsha
    Well, just to add a small element....
    You refer to the order by the Big O notation.
    Order for Linear Search is: O(n)
    and order for Binary Search is: O(log n).

    Cheers,
    Harsha.
    I thought that was a given.

  6. #6
    Registered User alice's Avatar
    Join Date
    Mar 2004
    Posts
    36
    then what is
    Worst case unsorted two-dimensional array of size N with linear search &
    Best case unsorted two -dimensional array of size N with linear search?

    I think the first one is log(NxN) / log 2 ?
    but what is the second one? I haven't any idea.

    or can someone told me where can I find more information(URL)?

    thk a lot.
    Last edited by alice; 06-05-2004 at 10:46 PM.

  7. #7
    Registered User CompiledMonkey's Avatar
    Join Date
    Feb 2002
    Location
    Richmond, VA
    Posts
    438
    Wouldn't the array be setup in such a way that you're only searching one of the two columns? Even if you did have to look at each column, I imagine you're looking at O(2n). I'm not sure about that though. Best case could be O(1) in any search.

  8. #8
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    Quote Originally Posted by alice
    Worst case unsorted two-dimensional array of size N with linear search &
    Best case unsorted two -dimensional array of size N with linear search?
    Worse case for unsorted arrays is always the number of elements, since the only way to search an unsorted array is by linear search.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM