Enthuware

I still don't understand the correct answer.

There are three possibilities.

1) if all elements in the array less than the search key, the insertion point is 4, thus -5 is returned.

2) if all elements in the array greater than the search key, the insertion point is 0, thus -1 is returned.

3) if any element in the array matches the search key, the value returned should range between -5 and -1.

So how can the values from 0 to 3 be returned?

What will it return if you search for "a", "aa", "aaa", or "aaaa"?
and what will it return if you search for "a ", "aa ", "aaa ", or "aaaa "?

HTH,
Paul.

Hi, I have been going through this question and am having trouble understanding the given answer.
It says that any number from -5 to 3 could be returned, however I do not see how -4, -3, or -2 can be returned as all of the values I have entered that are invalid return -5 whereas the blank search string returns -1.
I also think that, if we are required to place the elements of the array in to the search string when we are calculating the possible answers that the question could possibly need to be reworded as it is not altogether clear that this is what we are to do.
Could you help me clear this up?

You will get values from -1 to -4 if you search for A, aA, aaB, and aaaB
The explanation explains in detail why.

HTH,
Paul.

Thanks Paul, that's cleared it up for me.

public class LinkedListPeekDemo {
static String[] sa = { "a", "aa", "aaa", "aaaa" };
static {
Arrays.sort(sa);
}

public static void main(String[] args) {
String search = "";
if (args.length != 0)
search = args[0];
System.out.println(Arrays.binarySearch(sa, search));
}
}

if I execute the above program with "aaa " argument then the output is -4
so why is answer is "Any number from -5 to 3" ?

Please go through the explanation. It explains why in detail. Let me know if any statement is not clear.

This is simple as a cake. There are two cases:
1)the element to be searched is found in the array.
If it is found then the values at which the element is will be the same as the arrays indexes i.e. in the range of 0,1,2,3
2)the element to be searched in not found in the array
Then the method looks at the position at which the element should be inserted so that the array will be sorted(which if inserted the elements after it will need to be shifted one position to the right or increase one index of the array)
for ex. consider the array int a = {0,1,2,4}
now if you binary search 3, it is not present in the array but it can be inserted at the place of 4 and shift 4 to the next position and the method will return the index as -(i or the position at which the element should be inserted) - 1
in our case
-(3) - 1 = -4 and if we binary search 5 then it similarly returns -5 which is the minimum possible no for this method to result in our case and same for the test question.
And if the element -1 or any negative no is searched then it should be inserted at
the place of {>0,1,2,4} or at the 0th position in the array shifting 0 and the rest of the elements ahead which will cause the method to return
-(0) - 1 = -1. (So -1 is included in the output)
And lastly if you search the last element i.e. 4 it will return 3 which is the max possible index or the no to be returned by the binary search method.
So the range of the nos returned by the binary search method will be
-5(min) to 3(max)
I hope this explains the answer to those who are still unclear!

Dumb question, but how come when I run this code it always returns -1 ? If the first index is "a" shouldn't it return index 0? Why does it return undefined?

What was your command line argument?
If you are not passing anything, then it searches for "". This is not found and so the return value will be as per the formula (-(insertion point) - 1). "" will be inserted at 0th position, therefore, -0-1 = -1.

You might want to go through the explanation carefully because it explains all the possible outputs. Also, go through the post by jagoneye above.

Thanks. That was the problem. It was late and I'm getting burned out. For some reason I've been struggling with this for months, but for the insertion point I just find the index of where it should go, stick a - in front of it and decrement one time. So if it should be inserted at index 4, I convert that to -4, and then decrement once to -5. And that's my insertion point. I think.

I think that question should contain information about possible args, because it's not obvious from question that args could take any value.