answersLogoWhite

0

Linear search takes linear time with a worst case of O(n) for n items, and an average of O(n/2). Binary search takes logarithmic time, with a worst and average case of O(n log n). Binary search is therefore faster on average.

User Avatar

Wiki User

10y ago

Still curious? Ask our experts.

Chat with our AI personalities

JordanJordan
Looking for a career mentor? I've seen my fair share of shake-ups.
Chat with Jordan
LaoLao
The path is yours to walk; I am only here to hold up a mirror.
Chat with Lao
RossRoss
Every question is just a happy little opportunity.
Chat with Ross
More answers

Sequential search has a worst case of O(n) for n elements and an average of O(n/2). Binary search with a perfectly balanced binary tree or a sorted array takes O(n log n) time, both in the worst case and on average. However, an unbalanced tree has a worst case of O(n) when the tree is constructed from data that is already sorted or is in reverse order. So it is not true that a binary search algorithm is always faster, it is only faster when the structure is balanced and preferably perfectly balanced. Sorted arrays can always be regarded as being balanced but not necessarily perfectly balanced. A perfectly balanced tree has n levels such that the entire tree has 2^n-1 elements {0, 1, 3, 7, 15, 31, 63, ...} as defined by OEIS sequence A000225.

User Avatar

Wiki User

10y ago
User Avatar

A binary search is typically faster than a sequential search but requires that the data is sorted. Binary search has logarithmic time complexity whereas sequential search has linear time complexity.

User Avatar

Wiki User

10y ago
User Avatar

Binary search is, on average, much quicker than a linear search. Whereas a linear search must traverse the entire list or array in sequence to locate a matching element, binary trees search via a divide-and-conquer algorithm. If the tree is balanced, then half the list is automatically eliminated at each depth of the search, thus minimising the number of comparisons required overall. While a linear search may require fewer comparisons when the element is near the start of the list, elements towards the end of the list will require a good deal more comparisons. In terms of complexity, a linear search of n elements is O(1) for the first element, O(n) for the last and O(n/2) on average, whereas a binary tree has an average of O(n log n) if the tree is balanced.

User Avatar

Wiki User

12y ago
User Avatar

In sequential search, you have to check each element in the list one after another, with a worst case efficiency of O(n).

If you use binary search the list must be sorted), you are essentially cutting the remaining elements you must search in half with an efficiency of O(log n).

For example, searching for 9:

Sequential: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Binary: start at 4, 9 is higher you have 5 - 9 to the right. You check halfway through that "list", you see that 9 is larger than 7, so go right, repeat.

User Avatar

Wiki User

14y ago
User Avatar

The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element.

User Avatar

Wiki User

12y ago
User Avatar

Binary search is more efficient than linear search because we perform fewer comparisons on average. With linear search we can only eliminate one element per comparison each time we fail to find the value we are looking for, but with binary search we eliminate half the set with each comparison. For a set of n elements, the worst case is O(n) comparisons for a linear search and O(log n) comparisons for a binary search. Although there will be fringe cases where a linear search is quicker (such as when the set is particularly small or the values we seek are at or near the beginning of the sequence), we have to look at the worst case.

User Avatar

Wiki User

7y ago
User Avatar

yes alaways as.....this works on time o(logn).but sequential searches alaways works on complexity o(n^2).....so...it is faster

User Avatar

Wiki User

11y ago
User Avatar

yes, but it requires that the data be entered originally in a searchable tree format.

User Avatar

Wiki User

9y ago
User Avatar

Add your answer:

Earn +20 pts
Q: Advantages of binary search over sequencial search?
Write your answer...
Submit
Still have questions?
magnify glass
imp