aspose file tools*
The moose likes Performance and the fly likes Sequential search vs Binary Search test question. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Performance
Bookmark "Sequential search vs Binary Search test question." Watch "Sequential search vs Binary Search test question." New topic
Author

Sequential search vs Binary Search test question.

Aces Kok Ben
Ranch Hand

Joined: Apr 30, 2011
Posts: 44
I had the following question during my test however I don't know how to answer.

"Describe the changes needed if sequential search is used instead of binary search. Which approach is more efficient given that the retrieved Student arrayList is NOT sorted according to their admin number?" (4 marks)

From what I know, I think sequential search is less efficient because the algorithm search the whole list one by one, unlike the binary Search, which split the arrayList into 2 before searching, but I don't know if I'm correct. Anyone can help?
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12806
    
    5
Student arrayList is NOT sorted according to their admin number?


That is the key point.

If you are going to search for a specific admin number by binary search, the array MUST be sorted by admin number, thats the whole idea. If not sorted, how would you know which half to look in next?

Bill
Jeanne Boyarsky
author & internet detective
Marshal

Joined: May 26, 2003
Posts: 30762
    
156

Which makes the question:
do you think it is faster to sort the list and then do a binary search vs doing a sequential search with no sort.


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Aces Kok Ben
Ranch Hand

Joined: Apr 30, 2011
Posts: 44
Jeanne Boyarsky wrote:Which makes the question:
do you think it is faster to sort the list and then do a binary search vs doing a sequential search with no sort.


I think binary search is more faster. Because the using binary search, the program know where to search from, by splitting the arrayList into half.

Another question: Why is binary search algorithm called binary search? I don't see 1001010101001.
William Brogden
Author and all-around good cowpoke
Rancher

Joined: Mar 22, 2000
Posts: 12806
    
    5
Because the list is always split into two parts of course!

You can think of that as deciding one bit of an address if you like.

Bill
 
jQuery in Action, 2nd edition
 
subject: Sequential search vs Binary Search test question.