• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary search slower or faster than sequential search  RSS feed

 
Ranch Hand
Posts: 63
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
A binary search is usually slower than a sequential search on sorted array of data. Is there a definite answer to this question. I feel like it depends on the size of the array. If you have a sorted array that's big, then a binary search would be faster than a sequential search. If you have a sorted array that's small, then it'll be better to use the sequential array. What do you think?

Also, in a sequential search of a sorted array, you must examine the entire array if an item is not present in the array. I think this is false because if you list is sorted {1, 2, 4, 5, 6, 7, 8} and you wanted to find 3. You would stop after making comparing 3 with 4 since it is a sorted array, 3 will not be found above 4. Am I right??
 
author & internet detective
Marshal
Posts: 37518
554
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Conrado Sanchez wrote:A binary search is usually slower than a sequential search on sorted array of data. Is there a definite answer to this question. I feel like it depends on the size of the array. If you have a sorted array that's big, then a binary search would be faster than a sequential search. If you have a sorted array that's small, then it'll be better to use the sequential array. What do you think?

The worst case of a sequential search is larger than the worst case of a binary search for arrays that aren't tiny. But tiny is very small. Even with three elements, the worst case of a binary search is smaller than the worst case of a sequential search. At that size, ti is too small to matter though.

Conrado Sanchez wrote:Also, in a sequential search of a sorted array, you must examine the entire array if an item is not present in the array. I think this is false because if you list is sorted {1, 2, 4, 5, 6, 7, 8} and you wanted to find 3. You would stop after making comparing 3 with 4 since it is a sorted array, 3 will not be found above 4. Am I right??

That is correct. You know early on that the element isn't there and stop looking.
 
Sheriff
Posts: 4931
334
BSD
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Conrado Sanchez wrote:A binary search is usually slower than a sequential search on sorted array of data.
I wouldn't agree.

Binary search runs in O(logn) time complexity, where linear search runs in O(n). Defining the runtime, always being taken worst case scenario. Based on that knowledge, you could state opposite to your statement.

But there are more factors which needs to be taken into account. Is array sorted or not, how big it is and so on. Also it depends on application needs.

Let's see what other opinions you'll get.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37518
554
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Conrado,
Also, remember that people talk about either average or worst case performance time. You could always get lucky and find a match on the first element.
 
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Conrado Sanchez wrote:. . . if you list is sorted {1, 2, 4, 5, 6, 7, 8} and you wanted to find 3. You would stop after making comparing 3 with 4 since it is a sorted array, 3 will not be found above 4. Am I right??
You would have to iterate the whole list to confirm it is sorted by value before you would know to stop at 3. So I do not think that solution would work.

A binary search runs in O(logn) time, but the better sorting algorithms run in O(nlogn) time. If you have a 1000000 element list which you are searching once, it is quicker to do a linear search. Remember log₂1000000 ≅ 20. You might be able to do several linear searches in the same time as one sorting and one binary search. You will only notice an improvement for binary search if you search repeatedly. The exact performance depends on the sorting algorithm and the relative complexity of the equals and comparison methods and is difficult to predict.
 
Bartender
Posts: 10575
66
Eclipse IDE Hibernate Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Conrado Sanchez wrote:Is there a definite answer to this question.

Without knowing the exact amount of time each comparison takes, and the amount of time it takes to calculate a "midpoint" for each iteration of your binary search: No.

A general rule of thumb is that for up to ≈8 items, a sequential search is often just as quick, but even that is entirely dependant on how long each comparison takes.

Winston
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37518
554
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:
Conrado Sanchez wrote:. . . if you list is sorted {1, 2, 4, 5, 6, 7, 8} and you wanted to find 3. You would stop after making comparing 3 with 4 since it is a sorted array, 3 will not be found above 4. Am I right??
You would have to iterate the whole list to confirm it is sorted by value before you would know to stop at 3. So I do not think that solution would work.

I think we can assume the list is sorted for this discussion. Otherwise, you'd need to iterate the whole list to confirm it is sorted for binary search to which defeats the purpose.
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes, but only if you know the List is sorted beforehand. Look at the documentation for Collections#binarySearch() and it says you have to sort the List first. It also says (indirectly) that a linked list will have slower performance the binary search than an array list.
 
Jeanne Boyarsky
author & internet detective
Marshal
Posts: 37518
554
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell,
What I'm trying to say is that discussing the performance of binary vs sequential search only makes sense if the list is sorted.
 
Saloon Keeper
Posts: 18800
74
Android Eclipse IDE Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Back in school, I worked on a minicomputer system that introduced a sort/search library. Their search algorithms generally tried to pare down the candidate set to 10 elements or less. Once that was done, the remaining candidates were searched using a linear search, because the computational overhead for fancier algorithms was higher than simply using brute force when the set was that small.

There's no one-size-fits-all solution. You try and determine what the characteristics of the data being searched will be and adapt algorithms accordingly. And, bear in mind that in this era of cheap machines and expensive people, that at some stage the cost of human optimizing is likely to become more than the savings from running that much faster, so the absolutely fastest algorithm may not be a desirable goal, but simply getting an algorithm that's "good enough".
 
Campbell Ritchie
Marshal
Posts: 56600
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Agree. And sorry for throwing so many red herrings in yesterday.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!