Linear search vs Binary search

Oct 24, 2014 at 3:52pm
Can someone tell me what advantages could linear search have over binary search?
It seems to me like binary search is better in almost every way seeing as it's takes roughly half the time to search for something in binary search, while linear has to go through the set of arrays one by one to find the thing element searching for.
Last edited on Oct 24, 2014 at 3:55pm
Oct 24, 2014 at 4:01pm
In places where you can use binary search, you should do so. You are right that it is better.

The downsides I can think of are when using a binary search just isn't logically possible.
This would happen when the list is not sorted, or when the elements in the list are not comparable to each other.

Also, it doesn't take half the time for binary search, its proportional to the log (base 2) of the number of items in the list.
So if each index searched took 1 second, and you have 1024 elements in your array...
it would take worst case 1024 seconds to search linear,
and log(1024) == worst case 10 seconds to search binary. (Much faster than 512 seconds!)
Last edited on Oct 24, 2014 at 4:04pm
Oct 24, 2014 at 4:07pm
Also, it could be pretty difficult to do a binary search on a linked list. Some data structures don't lend themselves to binary searches
Oct 24, 2014 at 4:21pm
Depends on a lot of factors:

1. Is the data already sorted? If so, binary is obviously better.
2. How much data is there to search through?
3. How often do you need to search the array?

In some cases the processing overhead to perform a sort before a binary search might be more costly than a simple linear search. A sort requires you to access each element of the data at some point, so if you're going to do that, it only makes sense to do it if you need to repeatedly find something, and need to find it enough times to spend the time doing a sort.

The increase in advantage of binary over linear in a sorted array is logarithmically related to the size of the array:

For a random x in 1. . . n, the average linear search iterations would approximate n/2, whereas the number of iterations in a binary search is y, where 2^y >= n. For a 1024 term search, then, the average number of reads in a linear search is about 512, but the maximum number of reads in a binary search is 10 for every odd number, 9 or fewer for even numbers. Doubling the number of terms doubles the seeks in a linear search, adds one seek in a binary search.
Oct 24, 2014 at 8:53pm
Another reason is that binary search requires more code, so on a device with limited memory, linear search may be preferable.
Topic archived. No new replies allowed.