• 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

Insertion Point Question on binarySearch()

 
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


Results are:

four one three two
one = 1
--- reverse ---
two three one four
one = -1
one = 2


Why "-1"?
 
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The reason for the -1 is because binary search was not called using the same comparator that was used to
sort the array. According to the Sierra and Bates book, this will give an unpredictable result, in this case -1.
I am not sure why exactly -1, i.e what algorithm went wrong etc. But I don't think you need to go in to such depth
for the exam. Just remember that to use binary search on an array that is not sorted using natural order,you need
to use the comparator that was used to sort the array, otherwise the result will be unpredictable.

Martin
 
Sheriff
Posts: 11604
178
Hibernate jQuery Eclipse IDE Spring MySQL Database AngularJS Tomcat Server Chrome Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Erap,

Martin is spot-on and why it returns -1 is not explained, not in the K&B-book, not in the javadoc of the binarySearch-method. It just states that the result is undefined when the array is not sorted (or sorted with another comparator).

Kind regards,
Roel
 
Erap Estrada
Ranch Hand
Posts: 92
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Great. Thanks guys for the clarification.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic