This week's book giveaway is in the Other Languages forum.We're giving away four copies of Functional Reactive Programming and have Stephen Blackheath and Anthony Jones on-line!See this thread for details.
Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Output for Arrays.binarySearch()

Sandra Bachan
Ranch Hand
Posts: 434
Sun Web Learning Center code

According to Sun, two possible outputs are

-1 1

and

7 1

Where do the values of -1 and 7 come from. I can understand that Arrays.binarySearch("b") outputs 1 because that is where b is located AFTER sorting.

Need to understand what is going on BEFORE sorting.

Tom Reilly
Rancher
Posts: 618
Negative numbers are returned when the element that you are searching for cannot be found in the array so the binarySearch() method returns where it would have been found (minus 1) had the element been in the array. So -1 means position 0. I don't know about the 7 but here's a guess. There are many overloaded binarySearch() methods. The one the compiler chose is not seeing the array as an array of Strings. Which output did you get when you ran the test? If 7, you could put a breakpoint in the code and step into the binarySearch() method to see which one is actually called

EDIT: Thinking about it, my guess is probably completely wrong.

Tom Reilly
Rancher
Posts: 618
My test returned -1 1

Tom Reilly
Rancher
Posts: 618
I of course am assuming the 7 1 is a valid answer

Bert Bates
author
Sheriff
Posts: 8900
5
Hi Guys,

Where does it say that negative numbers are returned?

Tom Reilly
Rancher
Posts: 618
The API docs:
Returns:
index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the array: the index of the first element greater than the key, or a.length if all elements in the array are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Bert Bates
author
Sheriff
Posts: 8900
5
Doesn't that paragraph apply only to arrays that have been sorted? What does it say about unsorted arrays?

Tom Reilly
Rancher
Posts: 618
Also from the docs:
If it is not sorted, the results are undefined.

Stephan van Hulst
Bartender
Posts: 6326
78
Tom means that the negative number is returned in this particular case because it would place "b" before "d" since "d" is 'higher' than "b".

Bert Bates
author
Sheriff
Posts: 8900
5
Stephan - are you sure?

Tom - so what's your conclusion?

Stephan van Hulst
Bartender
Posts: 6326
78
Well, that's what I think. Now you're asking, no I'm not sure :P

Tom Reilly
Rancher
Posts: 618
• 1
Stephan - are you sure?

Tom - so what's your conclusion?

I think Sun's question is bogus because calling the binarySearch() method on an unsorted array returns undefined results but I tried to answer the original poster's question as best I could. As I understand the original question, -1 1 and 7 1 were both valid answers to the test question and an explanation was requested.

Bert Bates
author
Sheriff
Posts: 8900
5
Hey Tom,

I'm not trying to get you

I just think that some of the answers on this thread aren't quite accurate and I'm trying to help you guys sort them out.

For instance, why do you think Sun's answer is bogus?

Tom Reilly
Rancher
Posts: 618
• 1
For instance, why do you think Sun's answer is bogus?
Because one of the possible answers was not "results can not be determined"

Bert Bates
author
Sheriff
Posts: 8900
5
• 1
Isn't it true that the two answers we've been discussing would both be legal from a JVM's perspective?

Stephan van Hulst
Bartender
Posts: 6326
78
It seems completely arbitrary that Sun would pick these exact two answers though. That is probably their point, but they fail to convey to the original poster that these answers are in fact, arbitrary.

bhanu chowdary
Ranch Hand
Posts: 256
Sandra Bachan wrote:Sun Web Learning Center code
Need to understand what is going on BEFORE sorting.

Sandra, do you know how a binary search works? and regarding the answers

According to Sun, two possible outputs are
-1 1
and
7 1
Where do the values of -1 and 7 come from. I can understand that Arrays.binarySearch("b") outputs 1 because that is where b is located AFTER sorting.

I do not know what are the other options available apart from the above two, but i am guessing that only these two have their second output as 1. Since the question has "possible outputs" in it <any number> and 1 would do i guess.

Himanshu S. Soni
Greenhorn
Posts: 26
i get it how the output
-1 and 1 comes
but i have no clue how 7 comes in picture.

Before using BinarySearch, you need to know how this works.

Stephan van Hulst
Bartender
Posts: 6326
78
Doesn't matter. The designer is theoretically free to check whether the array is sorted, and if it isn't, return a completely random integer, just because he feels like it.

Bert Bates
author
Sheriff
Posts: 8900
5
On the real exam you're likely to encounter questions that contain phrases like:

- which are possible

or

- which are most likely

Most commonly these will be thread questions, based on the nature of threads, but I would say that a question like the one we're discussing here is also likely. So perhaps it's just about getting used to thinking this way... the "what's possible" perspective.

hth,

Bert

Sandra Bachan
Ranch Hand
Posts: 434
bhanu chowdary wrote:

Sandra, do you know how a binary search works?

I believe so...

bhanu chowdary wrote:

I do not know what are the other options available apart from the above two, but i am guessing that only these two have their second output as 1. Since the question has "possible outputs" in it <any number> and 1 would do i guess.

The choices were:

A 7 0
B 7 1
C 7 3
D -1 0
E -1 1
F -1 3

Correct options were B and E

Sandra Bachan
Ranch Hand
Posts: 434
Himanshu S. Soni wrote:i get it how the output
-1 and 1 comes
but i have no clue how 7 comes in picture.

Before using BinarySearch, you need to know how this works.

I thought I knew how BinarySearch works. Kindly point me in the right direction so I can understand how 7 is a possible answer.

Stephan van Hulst
Bartender
Posts: 6326
78
Haha, okay that explains a lot.

You don't need to know *anything* about binary-search. You just need to read what the contract for Arrays.binarySearch(Object[], Object) says.

Jim Ronholm
Greenhorn
Posts: 18
Hi Sandra

I'm certain that 7 is not a valid answer - at least not for that data set.

-1 is a possible value returned for "not found" - in the unsorted case that is what you will get for this search.

The reason that searching on an unsorted array is "undefined" is because it is possible that the value will be found, even though it is not in its "correct position." Consider for example the case where the value is randomly located at the exact centre of the array, then it will be found on the first iteration, at whatever position that happens to be. It might be found in other positions as well. However, it is also possible (far more likely actually) that it will never be found as the binary search successively narrows down the search set, eliminating half the possibilities each time - in this case it will return a negative value. You will only see positive values when the key is found, and in that case the positive value will be the position in the array where the key was found. In an array of length n, the largest possible positive value returned is n-1. In this case 3.

Jim

Bert Bates
author
Sheriff
Posts: 8900
5
Hey Jim,

Where does it say that that's how the JVM will behave?

Thanks,

Bert

Jim Ronholm
Greenhorn
Posts: 18
Bert - this has nothing to do with the JVM. It is the Arrays class from java.util. Tom has already quoted from the appropriate javadoc that says it will only return a positive value if the search key is found.

Any binary search will give you undefined results if you search on an unsorted set (not just in Java) - sometimes it will find the key, sometimes it won't depending on where the key value happens to lie.

There has been some implication that the BinarySearch in question examines the array to determine if it is sorted and then decides what to return - according to the source code it does not. It simply performs the search. Furthermore, if it did examine the array first and then choose what to return, it would no longer be undefined (since that just defined it). Lastly, such an action would, in a worst case scenario, require examining the entire array thereby reducing performance to that of a linear search - and eliminating the benefit of binary search in the first place.

Jim

Bert Bates
author
Sheriff
Posts: 8900
5
Hey Jim,

You're right, bringing in the JVM wasn't helpful...

Let me ask this another way - what does the API guarantee?

Jim Ronholm
Greenhorn
Posts: 18
As posted by others - positive values if found, negative values indicating where the value should be inserted if not found.

Since it can never be found in position 7 - it cannot be a valid answer.

I get a very strong feeling that you believe the code will return arbitrary values because of the sentence "undefined for unsorted arrays." Undefined is not the same as arbitrary, and binarysearch will not return arbitrary values. See my explanation above why the values returned from searching an unsorted array are meaningless/undefined (i.e. on any search it might return a found result, or a not found result, whether or not the key exists in the datataset).

I agree with Tom's reply that 7 is a bogus return value.

If you need additional proof - the binarysearch method is presented here (snipped from the full Arrays class written by Joshua Block et al - not my code). The first method delegates to the second, but notice that the upper limit will be governed by the length of the array. Even a fairly cursory examination will reveal that higher values are not possible since that value is never increased.

Stephan van Hulst
Bartender
Posts: 6326
78
You can't comment on whether undefined return values are arbitrary, because, well... they are undefined. They could very well be arbitrary. The fact that Sun's implementation isn't arbitrary, doesn't mean that I can't write an implementation that returns random values on an undefined result.

Bert Bates
author
Sheriff
Posts: 8900
5
Jim, I gotta say I think Stephan is on the right track.

What if Oracle decided they didn't like the way that the API was implemented? They wouldn't change the contract of the method, but they might change the algorithm.

Yet another way of thinking about this is from the OO perspective. While it's true that you can look at some source code, what's REALLY true is that you're not in charge of the code in the API. Best practices would dictate that your code assumes only what's guaranteed in the API.

Jim Ronholm
Greenhorn
Posts: 18
I hesitated to post the source code because I knew you would say that.

Bert and Stephan - the contract also includes the fact that this is a binary search.

What I am trying to say is that the return values are not undefined, merely what those results mean (the meaning of the results is undefined). The return values are clearly defined (the word undefined does not appear in the Returns: portion of the API doc). The results WILL be >= 0, indicating the position found, if and only if the key was found. They will be negative showing where the value should be inserted if not found. This is regardless of whether the array is sorted. However, on an unsorted array a positive return value has little meaning other than proving the key exists in the set (and where), but a negative value does not even prove the key isn't in the set. I.e. you can get a negative value even if the key is in the set.

The fact that results from a binary search on an unsorted array are undefined is specified by the "binary search algorithm" and repeated in the API documentation. This is not a choice made by those implementing it, and is a truth in both the OO world and outside of it.

If Oracle or Stephan decided to change the algorithm for this method - it would no longer be a binary search! This would be very bad form. If a different search algorithm is called for, then it should be either implemented in a new method indicating the new algorithm, or a more generically named method such as "search" (where the programmer would be free to choose any algorithm).

Stephan: I don't believe you (or anyone else) could write a binary search algorithm that "returns random values on an undefined result". To prove that a set is unordered (in the worst case) you would need to traverse the entire set thereby creating a linear search - so it would no longer be a binary search. If you don't prove that the set is unordered and you want to perform a binary search on it then you have to assume the set is ordered. Carry out the search and return whatever values you find. In that case it is important for user to know that the results are meaningless if they use your algorithm on an unordered set since the results will be undistinguishable from those returned from an ordered set (except in value).

I will concede that the writer of the question may have had the same view as you two (and as such the 7 1 answer would stand, as well as any other value for x in the form x 1), however if that is true then it ignores an understanding of a very important algorithm - and a misunderstanding of the API doc for this method.

Bert Bates
author
Sheriff
Posts: 8900
5
He Jim,

Let's remember that this forum is about the exam.

The objective is about understanding the API.

Talking about the in's and out's of a binary search algorithm is totally valid, but probably not in this forum. Well, I suppose it could be okay in this forum, but such discussions should clearly be labeled as being off-topic for the exam. This thread started off as a discussion of a mock exam question, not a review of algorithms. The API portions of the exam are focused on making sure that programmers know how to use the API and the docs for the API. For instance, the exam isn't focused on efficient hash codes, it's just focused on the contracts for hashCode() and equals(). One could argue that it's important to understand efficient hashing (which of course it is), but it's simply not on the exam.

hth,

Bert

Ranch Hand
Posts: 162
I have the similar question and feel that Sandra's question is not answered. Please advice what could be the possible value for "x" (I mean, before sorting) and how is it coming ? In the documentation, I see "If it is not sorted, the results are undefined. If the range contains multiple elements with the specified value, there is no guarantee which one will be found. "..In sandra's code snippet, there are only 4 elements. how could be the 7 as possible answer. I thought it should be between 0 and 3. Please advice.

Bert Bates
author
Sheriff
Posts: 8900
5
Hmmm...

I read the API again. It seems to me that the sentence you quoted is meant to stand on its own. It seems that subsequent sentences refer to different cases:

Searches the specified array for the specified object using the binary search algorithm. The array must be sorted into ascending order according to the natural ordering of its elements (as by the sort(Object[]) method) prior to making this call. If it is not sorted, the results are undefined. (If the array contains elements that are not mutually comparable (for example, strings and integers), it cannot be sorted according to the natural ordering of its elements, hence results are undefined.) If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

So my take is that this sentence: "If it is not sorted, the results are undefined.", stands on it's own.

If that interpretation is correct, then I would say that further analysis is simply going beyond what's guaranteed in the API contract.

Ranch Hand
Posts: 162
Hi, Please advice why I am getting output as 3..I thought it would be 0 or 5.

Jim Ronholm
Greenhorn
Posts: 18
Sorted list
0 Russia
1 Russia
2 Russia
3 Russia
4 Russia
5 Russia
6 UK
7 USA

BinarySearch starts at the middle location. In this case it finds the key on its first comparison. Bert will tell you that it doesn't matter that it is a BinarySearch though (therefore you should ignore the algorithm) and you should expect any answer ranging from 0 through to 5 since the contract states "If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found."

Ranch Hand
Posts: 87
thanks

Bert Bates
author
Sheriff
Posts: 8900
5
Hi Guys,

Let's clarify a few things...

BinarySearch starts at the middle location. In this case it finds the key on its first comparison. Bert will tell you that it doesn't matter that it is a BinarySearch though (therefore you should ignore the algorithm) and you should expect any answer ranging from 0 through to 5 since the contract states "If the array contains multiple elements equal to the specified object, there is no guarantee which one will be found.

This discussion is all about context.

Here are a couple of contexts that seem to be at play here:

1 - From a computer science perspective how does a binary search algorithm work?
2 - From the certification perspective how should you interpret such a question?
3 - From the OO perspective how should you work with an API?

I think that everything Jim is saying is accurate... from the first perspective.

I think that in this forum, it's FAR more important to keep the second and third perspectives in mind.

Harikrishna Gorrepati
Ranch Hand
Posts: 423
Hi, Could you please advice why I am getting the output as -1 even though I sorted the array. I thought it should print "2" because sorted array contains [two, threee, one, four]

Jim Ronholm
Greenhorn
Posts: 18
New questions really should go into a new thread.

... but the answer is simply that your Comparator causes the arrays to be sorted into descending order "according to the natural ordering of its elements", not ascending. The algorithm ignores the part of the array containing the key, so it is never found.

Be very careful with test data. If you had tried it with "one", "two", "four", "five" then it would have been found (and you would not have known about the logic error). This is the warning about "undefined" already discussed at length.

If you want it to work with data in this order, you will have to work with classes that naturally order themselves in the order you sort them. (Note: String isn't a class you can extend, so you will need to build a new class that encapsulates a String.) If you want to see more on that you should repost in a new forum/thread and send me a message and I'll respond there.