This week's book giveaway is in the Android forum.We're giving away four copies of Head First Android and have Dawn & David Griffiths on-line!See this thread for details.
Big Moose Saloon
 Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies Register / Login Win a copy of Head First Android this week in the Android forum!

# problem in Arrays.binarySearch method

Mahendran Aiyappan
Ranch Hand

Joined: Sep 05, 2005
Posts: 102
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.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9374

19

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.

SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Mahendran Aiyappan
Ranch Hand

Joined: Sep 05, 2005
Posts: 102
Got it.

Thanks Ankit.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14916

26

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

Joined: Dec 17, 2007
Posts: 180

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)
Seema Gaurav
Ranch Hand

Joined: Apr 29, 2008
Posts: 47
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

Joined: Sep 05, 2005
Posts: 102
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.

subject: problem in Arrays.binarySearch method