- Forum
- General C++ Programming
- Linear search vs Binary search
Linear search vs Binary search
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.
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
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!)
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
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
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.
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.
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.