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??

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.

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

I wouldn't agree.Conrado Sanchez wrote:A binary search is usually slower than a sequential search on sorted array of data.

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.

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.

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

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.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??

A binary search runs in O(log

*n*) time, but the better sorting algorithms run in O(

*n*log

*n*) 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.

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

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here

Campbell Ritchie wrote: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.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??

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.

[OCA 8 book] [OCP 8 book] [Practice tests book] [Blog] [JavaRanch FAQ] [How To Ask Questions] [Book Promos]

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

What I'm trying to say is that discussing the performance of binary vs sequential search only makes sense if the list is sorted.

Other Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, TOGAF part 1 and part 2

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".

An IDE is no substitute for an Intelligent Developer.