• 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

K & B book p. 659 - Explanation to self test question 16

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

In the explanation to this question it says:

... Note that when the binarySearch() returns an "undefined result" it does not officially have to be -1, but it usually is, ...



In the question the array was not sorted properly before doing the binarySearch() and therefore the result is undefined. I thought this means if the searched element is in the array it could be found or not. If not found the return value would be (-(insertion point) - 1), whereby insertion point could be anywhere in the array.
So -1 would be the return value only if the binary search algorithm 'thinks' the element has to be inserted at position 0?

Any explanations?

Thanks,

John
 
Ranch Hand
Posts: 142
Netbeans IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Dear John,
Please check out the explanation on page 576-577 of the same book


Unsuccessful searches return an int index that represents the insertion point.
The insertion point is the place in the collection/array where the element
would be inserted to keep the collection/array properly sorted. Because positive
return values and 0 indicate successful searches, the binarySearch()
method uses negative numbers to indicate insertion points. Since 0 is a valid
result for a successful search, the first available insertion point is -1. Therefore,
the actual insertion point is represented as (-(insertion point) -1). For
instance, if the insertion point of a search is at element 2, the actual insertion
point returned will be -3.



Cheers
Meherdad
 
reply
    Bookmark Topic Watch Topic
  • New Topic