wood burning stoves 2.0*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Arrays.binarySearch()  query 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 "Arrays.binarySearch()  query" Watch "Arrays.binarySearch()  query" New topic
Author

Arrays.binarySearch() query

Moieen Khatri
Ranch Hand

Joined: Nov 27, 2007
Posts: 144
Hi,

Can someone explain the below question from K & B collections chapter:

Question:

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


I didn't understand this question and the solution explaination given below:

G is correct. 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.


Please can someone explain this with an example?

Thanks
Serg Masow
Ranch Hand

Joined: Dec 17, 2007
Posts: 49
Hi Moieen,

assume you have a sorted array with five elements like this
int[] array = { 0, 2, 4, 6, 7 };

If you search for an element which is present in array for example 4
int result = Arrays.binarySearch(array, 4);

your result will be the index of the element in this array: 2.
If you search for an element, which is not in array, for example 5
the result is an negative number, which represents an insertion point of this element to keep the array sorted. Imagine you have to put 5 in this array so that array stay sorted. The new array would be { 0, 2, 4, 5, 6, 7 }. The position of 5 would be 3. The result of binarySearch() is the fictive position of 5 in the new array negated and decremented ( -3 - 1 = -4). The result of search is -4.

The maximum positive result of the binarySearch() is the biggest index of the array ( which is in this example 4 ) and the minimum insertion point is the fictive position after the element 7 which is -6. So the range of the search results is from -6 to 4.

Sorry for my poor English


SCJP 6.0 [95%] OCP EJBD 6.0 [93%]
Moieen Khatri
Ranch Hand

Joined: Nov 27, 2007
Posts: 144
Thanks Serg

So what I get from your explaination is that maximum positive range is the size of array + 1
Moieen Khatri
Ranch Hand

Joined: Nov 27, 2007
Posts: 144
Thanks Serg

So what I get from your explaination is that maximum positive range is the size of array - 1 and negative range is -(Size of the array ) - 1

Please correct me if I am wrong here
[ January 03, 2008: Message edited by: Moieen Khatri ]
Serg Masow
Ranch Hand

Joined: Dec 17, 2007
Posts: 49
Hi Moieen,

you got it, your last post is absolutely correct.
 
jQuery in Action, 2nd edition
 
subject: Arrays.binarySearch() query
 
Similar Threads
Question regarding binarySearch....
Binary Search doubt
binarySearch(). (Objective 6.5)
binary search
problem in Arrays.binarySearch method