Not able to understand the output

[Sonali Sehgal]

This is an Enthuware question:-

   

import java.util.*;
public class TestClass 
{	
    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));
    }
}


 

What all can this program print when run?

correct Answer is Any number from -5 to 3.


I do understand the explanation enthuware gives me:-


It is imporant for you to understand what binarySearch(...) method returns:

public static int binarySearch(Object[] a, Object key)
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 Sort(Object[]), above) 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 order 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.

Parameters:
a - the array to be searched.
key - the value to be searched for.
Returns:
index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size(), if all elements in the list 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.

Throws:
ClassCastException - if the search key in not comparable to the elements of the array.



Please can someone explain the output of this program to me ???

[Jason Irwin]

Err....if you understand the Enthuware explanation, why do you not understand the output?

Have you tried running the code and exploring the behaviour for yourself?

[Sonali Sehgal]

Hi Jason yes I did tried running the code and the output is -1 but how does it come as -1 and where do these numbers come from....whereas array had nothing to do with numbers or probably it is not that much clear......to me..........can you help???


or I can ask like:-

   
System.out.println(Arrays.binarySearch(sa, search));   
 

the above line of code prints out as -1 ...How does searching gives -1 and not any other array element???

[Sachin Adat]

Do you know what the int returned by binary search means..........?

[Sonali Sehgal]

Hi Sachin,

No that is exactly my question what does int returned by Binary search means and How and where does this int comes from??

[Jason Irwin]

The description of what the int means is in Enthuware's explanation!

In the case of no args being passed, search is "".
This does not exist in the array, so binarySearch will return "-(insertion point) - 1" (as stated in the Enthuware explanation)
The insertion point for "" is 0 (it comes before "a" in natural order).
-(0) is still 0.
0 - 1 = -1 and so that is what you get.

[Sonali Sehgal]

Thanks a lot Jason.I understood the whole program and the output now....

[Sachin Adat]

API wrote: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.

In short, it means if the search is successful, it will return the index of the found object.
If its unsuccessful, it will return the index where the searched object can be inserted so that the list will remain sorted.
So, if the searched object is to be inserted at 2nd position -3 will be returned.
In the above example, the search is unsuccessful and the new String object is to be inserted at the 0th position(spaces come before alphabets).
So you get -1 as the output. Every time, a binary search will return you an int between -(n+1) to n-1 where n is the length.

HTH

[Sonali Sehgal]

Thanks a ton Sachin...
Now I understand how does it comes as -5 to 3 as the answer any number.

[Sonali Sehgal]

Hi Sachin,

I have one more question you said that

"So, if the searched object is to be inserted at 2nd position -3 will be returned. "

How do we perform this program of inserting at 2nd postion...???

[Sachin Adat]

Sonali Sehgal wrote:How do we perform this program of inserting at 2nd postion...???

We cannot perform that operation, as you cannot change the length of an array.
But if -3 is returned, it means that the search you did was unsuccessful(because of the minus sign),
and if you want to insert this value in the array and keep it sorted, insert it in the 3rd position(0 based will make it index[2]).
How you do it, depends on you (create a new array and insert it). I don't know of any method in the APIs that does it.

[Sonali Sehgal]

Thank you Sachin for helping me.

[Mo Jay]

Sorry Sonali but you don't seem to understand the purpose of the binarySearch() method, here below try this modification of your code to see how it will return -3.

  static String[] sa = { "a", "aa", "aaaa", "aaaaa" };  

Do you see the strings of a's above in the String array, I have skipped "aaa" and since the method is about the order then if you compile the program with the String above. Try to run the program as: java TestClass aaa, the result will be -3 because the 3rd position is where aaa needs to be inserted to keep the String array sorted in ascended order.

Hope this helps.
Cheers!!!