Win a copy of Kotlin in Action this week in the Kotlin forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Arrays.binarySearch() query

Moieen Khatri
Ranch Hand
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
Posts: 50
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
Ranch Hand
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
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
Posts: 50
Hi Moieen,

you got it, your last post is absolutely correct.

 It is sorta covered in the JavaRanch Style Guide.