# Question regarding binarySearch....

Justin Smith

Greenhorn

Posts: 19

posted 7 years ago

- 0

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

And the answer is given as G. As per my understanding the binarysearch index would return -1 if the match is not found since 0 is also considered as a successful match. So for 0 it is -1, 1 it is -2 and so on until 4 it is -5. So as per my understanding the answer would be E. Isn't it? Please clarify.

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

And the answer is given as G. As per my understanding the binarysearch index would return -1 if the match is not found since 0 is also considered as a successful match. So for 0 it is -1, 1 it is -2 and so on until 4 it is -5. So as per my understanding the answer would be E. Isn't it? Please clarify.

Ralph Jaus

Ranch Hand

Posts: 342

Raphael Rabadan

Ranch Hand

Posts: 141

posted 7 years ago

- 0

Page 556/557 of K&B 5 Book's

Regarding binarySearch

[ July 24, 2008: Message edited by: Raphael Rabadan ]

Regarding binarySearch

Unsuccessful searches return an int index that represents theinsertion point.

The insertion point is the place in the collection/array where the element

would be insertedto keep the collection/array properly sorted. Because posi-

We�ve talked a lot about sorting by natural order and using Comparators

to sort. The last rule you�ll need to burn in is that, whenever you want to sort an array

or a collection, the elements inside must all be mutually comparable. In other words, if you

have an Object[] and you put Cat and Dog objects into it, you won�t be able to sort

it. In general, objects of different types should be considered NOT mutually comparable,

unless specifically stated otherwise.

tive return values and 0 indicate successful searches, the binarySearch()

method uses negative numbers to indicate insertion points.Since 0 is a valid.

result for a successful search, the first available insertion point is -1. Therefore,

the actual insertion point is represented as (-(insertion point) -1). For

instance, if the insertion point of a search is at element 2, the actual insertion

point returned will be -3

[ July 24, 2008: Message edited by: Raphael Rabadan ]

Justin Smith

Greenhorn

Posts: 19

posted 7 years ago

- 0

Thanks Ralph and Raphael for your reply... But this is where i am getting stuck.

"Since 0 is a valid result for a successful search, the first available insertion point is -1. Therefore,the actual insertion point is represented as (-(insertion point) -1). Forinstance, if the insertion point of a search is at element 2, the actual insertion point returned will be -3."

So the insertion point for the 5th element (4th in index) is going to be

-5 right, how did we get to the -6, is that means say i have an array of 10 elements (0 to 9), the values would be from -11 through 9, is that the answer for the question then.....

"Since 0 is a valid result for a successful search, the first available insertion point is -1. Therefore,the actual insertion point is represented as (-(insertion point) -1). Forinstance, if the insertion point of a search is at element 2, the actual insertion point returned will be -3."

So the insertion point for the 5th element (4th in index) is going to be

-5 right, how did we get to the -6, is that means say i have an array of 10 elements (0 to 9), the values would be from -11 through 9, is that the answer for the question then.....

Ralph Jaus

Ranch Hand

Posts: 342

posted 7 years ago

- 0

Given a = {0,1,2,3,4}. Because the array doesn't contain 5, Arrays.binarySearch(a,5) looks at what position the 5 is to be inserted to keep the array sorted. And that's the position with index 5. Therefore the result is -(5) -1 = -6.

[ July 24, 2008: Message edited by: Ralph Jaus ]

[ July 24, 2008: Message edited by: Ralph Jaus ]

SCJP 5 (98%) - SCBCD 5 (98%)

Justin Smith

Greenhorn

Posts: 19

Raphael Rabadan

Ranch Hand

Posts: 141

Ralph Jaus

Ranch Hand

Posts: 342

posted 7 years ago

- 0

Hi Justin, you're right.

By the way, the satements

-----------------------------------------

SCJP 1.5 (98%)

By the way, the satements

are wrong. -1 is returned, if the the element used in binarySearch is less than the smallest element in the array (that is, it has to be inserted at position 0 to keep the array sorted). Let a = {0,2,4,6,8}. Than Arrays.binarySearch(a,1) would return -2, because 1 has to be inserted at index position 1 to keep the array sorted. And so on.No insert Point --> -1

At 0 --> -2

At 1 --> -3

At 2 --> -4

At 3 --> -5

-----------------------------------------

SCJP 1.5 (98%)

SCJP 5 (98%) - SCBCD 5 (98%)

Ralph Jaus

Ranch Hand

Posts: 342

Raphael Rabadan

Ranch Hand

Posts: 141

Justin Smith

Greenhorn

Posts: 19

Ralph Jaus

Ranch Hand

Posts: 342

It is sorta covered in the JavaRanch Style Guide. |