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

problem in Arrays.binarySearch method

Ranch Hand
Posts: 102
• Number of slices to send:
Optional 'thank-you' note:
Hi Guys,

Given a properly prepared String array containing five elements, which range of results could a
proper invocation of Arrays.binarySearch() produce?
A. 0 through 4
B. 0 through 5
C. -1 through 4
D. -1 through 5
E. -5 through 4
F. -5 through 5
G. -6 through 4
H. -6 through 5

Explanation given in the book is:

If a match is found, binarySearch()will return the index of the element that
was matched. If no match is found, binarySearch() will return a negative number that,
if inverted and then decremented, gives you the insertion point
(array index) at which the
value searched on should be inserted into the array to maintain a proper sort.

I have some problem in understanding this answer. The problem I have marked in bold.

Thanks,
Mahendran.

Sheriff
Posts: 9707
43
• Number of slices to send:
Optional 'thank-you' note:
Well take this example

int[] arr = {10,20,30,40};
Arrays.binarySearch(15);

now as you can see that 15 is not in the list. But if you want to keep your array sorted, then you must insert 15 at index 1 i.e. between 10 and 20. So the returned value will be -2. If you invert the value of -2 (by doing 1's complement as ~(-2)), you will get 1. Similarly if you search for 45, you will get -6 as inverting -6 will result in 5 which is the correct position for 45.

Mahendran Aiyappan
Ranch Hand
Posts: 102
• Number of slices to send:
Optional 'thank-you' note:
Got it.

Thanks Ankit.

Java Cowboy
Posts: 16084
88
• Number of slices to send:
Optional 'thank-you' note:

Originally posted by Mahendran Shanmugam:
Explanation given in the book is:

Which book? Remember, you are required to quote your sources when you post a question copied from a book.

Ranch Hand
Posts: 180
• Number of slices to send:
Optional 'thank-you' note:
Hi ,Ankit I think you have mistakenly write:-

int[] arr = {10,20,30,40};
Arrays.binarySearch(15);
//compilation fail

it would be Arrays.binarySearch(arr,15)

Ranch Hand
Posts: 47
• Number of slices to send:
Optional 'thank-you' note:
Hey Ankit,
You have got the concept right, but a small mathematical correction in your explanation. Caught this because I go wrong with it all the time

In the code you mentioned, the output of executing

will be -5 and not -6.

The easiest way to remember this as mentioned in KB is [-(index)-1]=-4-1=-5
Thanks,
Seema

Mahendran Aiyappan
Ranch Hand
Posts: 102
• Number of slices to send:
Optional 'thank-you' note:
The Book Name is :

SCJP Sun Certified Programmer for Java 5 Study Guide (Exam 310-055)
by Katherine Sierra (Author), Bert Bates (Author)

Thanks,
Mahendran.