Prev: Modular inverse function
Next: Tree from inorder and pre-order traversals
From: sophia on 14 Apr 2008 08:48
Dear all,

In which all situations linear search will be more efficient than
binary search ?
From: [Jongware] on 14 Apr 2008 08:49
sophia wrote:
> Dear all,
>
> In which all situations linear search will be more efficient than
> binary search ?

Unsorted data.

[Jw]
From: Richard Harter on 14 Apr 2008 10:52
On Mon, 14 Apr 2008 05:48:19 -0700 (PDT), sophia
<sophia.agnes(a)gmail.com> wrote:

>Dear all,
>
>In which all situations linear search will be more efficient than
>binary search ?

I assume that the data is sorted; if it is not the question is
moot. Your question really doesn't have an answer until you
specify what is meant by "more efficient". How are you measuring
efficiency? A further issue is that performance is variable,
depending on the item being searched.

That said, in terms of wall clock time, linear search will run
faster than binary search on average for N<C where N is the data
set size and C is an implementation specific constant that
depends upon the costs of various operations. A critical factor
is whether you can place a sentinel in the data. If you can the
value of C approximately doubles. Here are some typical values
for C:

C = 12, if sentinels are not permitted
C = 25, if sentinels are permitted.
C = 50, if sentinels are permitted and do one bisection

Incidentally, what you do in a sentinel based search is to place
the value you are searching for at the end of the array you are
searching. By doing this you eliminate the need to check for
having exhausted the array since you are guaranteed to find the
item.

Richard Harter, cri(a)tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
From: Bartc on 14 Apr 2008 12:43

"sophia" <sophia.agnes(a)gmail.com> wrote in message
news:1f15048d-2b51-4ba9-8c3b-ddc2614c9f9e(a)b5g2000pri.googlegroups.com...
> Dear all,
>
> In which all situations linear search will be more efficient than
> binary search ?

I suppose, if the most common items at the beginning of the list, a linear
search could be better.

It's certainly a lot simpler. I use linear searches a lot, and I only get
around to upgrading them if they are a bottleneck. Then I might use a
hashtable.

--
Bart


From: Andrey Tarasevich on 18 Apr 2008 15:18
sophia wrote:
>
> In which all situations linear search will be more efficient than
> binary search ?

Outside of any context? It could be more efficient in practice when the
number of elements to be searched is small.

In context? Well... That could be the case, for example, in contexts
when you have to do _many_ search operations in sequence knowing in
advance that the total complexity is well-limited.

Let me illustrate this by a simple example. Let's say you have two
sorted arrays - A and B of sizes M and N - as input. You have to produce
third sorted array - C of size M+N - as output by merging the input
arrays. This is the classic well-known problem of merging two sorted
sequences. This problem is solved by the classic well-known sequential
algorithm:

- Just compare the first elements of A and B, choose the smaller one
and move it to C
- Repeat until done.

This algorithm requires O(M+N) comparisons.

If you take a careful look at this algorithm, you'll be able to see that
it can be reformulated in the following manner:

- Take the first element 'a' from A, find the correct place of 'a' in
B (as if you wanted to insert 'a' into B) by using _linear_ search in B
- Move leading elements of B (up to the found "insertion" point) to
C, then move 'a' to C
- Repeat until done.

This description sounds different from the original one, but in fact it
is exactly the same algorithm, it's just seen from a different point of
view. Of course, the number of comparisons is the same - O(M+N).

Now, a person who knows that binary search is generally more efficient
than a linear one might immediately come up with an obvious idea: what
if in the above algorithm we use binary search instead of the linear
one. This will surely improve its performance!

It is easy to show that if we use the binary search in B in the latter
algorithm, the required number of comparisons would be described by
O(M*log2 N).

This means that when the values of M and N are pretty close to each
other, the linear search based algorithm will win considerably over the
binary search based algorithm. The binary search based algorithm starts
to win only when M << N.

Why does it happen? It happens because the linear-search based algorithm
in this case happens to exploit very well the incremental asymmetrical
nature of linear search. In this case linear search begins from the
first element of array B, stops at some location, then continues from
the previous location and so on until the end of array B is finally
reached. Every time only some _prefix_ of B is considered and during the
entire algorithm the array B is looked through once and only once.
Binary search is different. It always have to take into account the
entire reminder of the array. This is what works against it in the end.
If the number of binary search invocations is small (M << N), binary
search wins, otherwise it loses.

So that's one example for you: when you merge two sorted sequences using
the "classic" merging algorithm, what you essentially do is a repetitive
linear search and, if the input sequences have about the same length,
this linear search works much more efficiently than binary search (in
the context of the entire algorithm).

As an additional remark, I'll note here that the optimal (in therms of
number of comparisons) merging algorithm for arbitrary values of M and N
is actually a blend of linear and binary searches: first you perform a
"stepped" linear search for a correct segment in B and then perform a
binary search inside the segment.

--
Best regards,
Andrey Tarasevich
 | 
Pages: 1
Prev: Modular inverse function
Next: Tree from inorder and pre-order traversals