This week's giveaway is in the Spring forum.
We're giving away four copies of Learn Spring Security (video course) and have Eugen Paraschiv on-line!
See this thread for details.
Win a copy of Learn Spring Security (video course) this week in the Spring forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Sequential search vs Binary Search test question.

 
Aces Kok Ben
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 13055
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 34071
331
Eclipse IDE Java VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Aces Kok Ben
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 13055
6
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic