• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

problem in Arrays.binarySearch method

 
Mahendran Aiyappan
Ranch Hand
Posts: 102
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

The Answer is: G

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.

Please give some sample example

Thanks,
Mahendran.
 
Ankit Garg
Sheriff
Posts: 9528
33
Android Google Web Toolkit Hibernate IntelliJ IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Got it.

Thanks Ankit.
 
Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15452
42
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Ashok Pradhan
Ranch Hand
Posts: 180
Eclipse IDE Firefox Browser Netbeans IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic