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.

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

thk a lot.

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