Arrays.binarySearch() query

[Moieen Khatri]

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]

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

[Moieen Khatri]

Thanks Serg

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

[Moieen Khatri]

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]

Hi Moieen,

you got it, your last post is absolutely correct.