# Thread: no. of comparisons in linear/binary search

1. ## 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. 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. 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.

4. 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. 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. 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.