Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

About binarySearch throu arrays or Lists

 
Vadim Vararu
Ranch Hand
Posts: 147
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There is an afirmation in SCJP preparation book: "To be searched (via binarySearch method), an array or a List must first be sorted".
Tell me, please, why do i have to sort firstly the list in order to search via binarySearch method?

Thanks, Vadim Vararu.
 
Vadim Vararu
Ranch Hand
Posts: 147
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, i've searched it and found that it is necessary because the algorithm of binary search can be applied only on sorted lists (arrays).
 
Christophe Verré
Sheriff
Posts: 14691
16
Eclipse IDE Ubuntu VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The algorithm used in the binarySearch assumes that the array is sorted. This is a precondition. This is how some sorting algorithms work. Searching for items in a collection is often more efficient when the collection is properly sorted.

Details about the binary search algorithm here.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic