wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Chap 7 pg  628 from kathy & Sierra Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Murach's Java Servlets and JSP this week in the Servlets forum!
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Chap 7 pg  628 from kathy & Sierra" Watch "Chap 7 pg  628 from kathy & Sierra" New topic
Author

Chap 7 pg 628 from kathy & Sierra

aslika bahini
Ranch Hand

Joined: Mar 03, 2007
Posts: 111
Hi There,

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

I am not able to understand the answer. Can any of you please explain?

Thanks
Saritha
Sandhya Bhaskara
Greenhorn

Joined: Jun 29, 2005
Posts: 23
Match not found "A" "C" "E" "F" "G" "H"
Insert element
at index -1 -2 -3 -4 -5 -6

Array elements "B" "D" "F" "H" "J"

Match found 0 1 2 3 4


Consider that an array has the strings "B","D","F","H","J", . If match is found he binarySearch method returns the index of match. So it can return values from 0 to 4 if match is found

If match is not found it will return the index where the element could have been inserted
Eg:"A" is not in the array but the correct index where "A" can be inserted is 0. Since 0 is already valid it will return -1.
Similarly for "C" it would return -2 since "C" should go between B and D(0 and 1 index)
"K" would be inserted after "J" and hence -6(See above).
Basically we can insert an element that is not found either at the begining of array or end of the array or inbetween the array elements.


Sandhya Bhaskara<br />SCJP 1.4,SCWCD 1.4,SCBCD 1.3,SCJP 6
Sandhya Bhaskara
Greenhorn

Joined: Jun 29, 2005
Posts: 23
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

remember that if a match is not found, binarySearch returns 1's complement of the place where the element should be inserted.

So if the element should be inserted at index 0, it will return -1(1's complement of 0 is -1). Similar is the case for all the indexes.

If you take 1's complement of the negative value that it returns, you will get the index of the location where the element must be inserted. So 1's complement of -1 is 0....


SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Rekha Srinath
Ranch Hand

Joined: Sep 13, 2008
Posts: 178
To give you a formula for this, the value returned in case of unsuccessful searches will be (-insertionpoint-1), where "insertionpoint" is the zero-based index location where the element could have been inserted.
Taken from: Pg #577, K&B-310-065.

So, for an array of 5 elements, the index locations are from 0 to 4. Hence, on the other end, a new element can be inserted at index 5. As per the formula, the method returns (-5-1) which is -6.

So, the range of values is -6 till 4
[ October 10, 2008: Message edited by: Rekha Srinath ]
Christophe Verré
Sheriff

Joined: Nov 24, 2005
Posts: 14687
    
  16

(Just ignore this. I can't resist mentioning that "kathy & Sierra" in the thread title is the same person )


[My Blog]
All roads lead to JavaRanch
aslika bahini
Ranch Hand

Joined: Mar 03, 2007
Posts: 111
Thanks to all. It helped a lot.

Saritha
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Chap 7 pg 628 from kathy & Sierra
 
Similar Threads
k&b scjp5, page no 616, problem no 9
binary search
K&B Book Chapter 7,Page 616,Question 9
Kathy Sierra doubt
doubt in generics- K&B book