• 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

Binary search() method in Collections

 
Ranch Hand
Posts: 30
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hello Ranchers,
I've read a lot about binary search()method but i couldn't understand it and how it works and i want someone to explain it and how it works to me.
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
A binary search requires elements to be sorted. Basically, it looks at the element in the middle of the list and compares it to the element it's looking for. If that happens to what it's looking for, then it's done. Otherwise, based on the comparison -- and assuming that the list is sorted in ascending order -- it narrows the search to either the first half of the list or the second half of the list. For example, if I'm searching for "75" and the middle element is "50," then 75 (if present at all) must be in the second half of the list, so I can forget about the first half. This process repeats until the element is found or the list runs out of elements.

As you can see, if the elements are not sorted before the binary search is performed, then the results will be unpredictable, because each decision about whether to narrow the search to the first or second half will not have a basis.
[ July 31, 2007: Message edited by: marc weber ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic