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.

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

posted

0

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

posted

0

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 ]