• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Sequential search vs Binary Search test question.

 
Ranch Hand
Posts: 44
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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?
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
author & internet detective
Posts: 41860
908
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic