binarySearch() method of Arrays

[Astha Sharma]

import java.util.*;
class SearchObjectArray
{
	public int copareTo(Object g)
	{
		return 0;
	}
    public static void main(String args[])
    {
   		String[]sa={"one","two","three","four"};
   		Arrays.sort(sa);
   		for(String s:sa)
   		System.out.print(s+" ");
   		System.out.println("\n"+Arrays.binarySearch(sa,"one"));
   		ReverseSort rs=new ReverseSort();
   		Arrays.sort(sa,rs);                       //line1
   		for(String s:sa)
   		System.out.print(s+" ");
   		System.out.println("\n"+Arrays.binarySearch(sa,"one",rs));                  //line2
   	}
   	static class ReverseSort implements Comparator<String>
   	{
   		public int compare(String a,String b)
   		{
   			return b.compareTo(a);
   		}
   	}
}

gives the output-

four one three two
1
two three one four
2


At line1, we have a sorted array of strings 'sa'. Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument? Why the 'two argument' version of this method doesn't work here and gives unpredictable output?

[Anayonkar Shivalkar]

Hi Astha Sharma,

I assume you've understood all 4 lines of output. If yes, then the questions are quite straightforward.

Astha Sharma wrote:Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument?

This is because, at line no. 16 of your snippet, you've sorted the array as per your own comparator (which sorts array in reverse order). Now, when you perform a binary search, the default logic (i.e. 2 arg method) assumes that array is sorted by default order (e.g. alphabetically in case of String etc.) and will try to search the array, but as we know that the array is not sorted as per default ordering, but as per ReverseSort ordering.
So, there should be a way to tell binary search algorithm that by what logic the array is sorted, then only it will be able to search the array properly. Otherwise, it would assume that array is sorted with default logic, and will give 'unpredictable result'.

I hope this helps.

By the way, you can get more info about questions like this by simply looking at JavaDoc of class/method.

[Zeeshan Sheikh]

At line1, we have a sorted array of strings 'sa'.

//line 1: Searches the specified array (sa) for the specified object (rs) using the binary search algorithm.

Then at line2, why the overloaded version of method binarySearch() is needed which takes a Comparator as an argument?

Its the logic whoever wrote the program !! The following method is used

//line 2: Method Signature: public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)
The array to be searched is sa
key the value to be searched for is one
c the comparator by which array is ordered (rs). (which is why comparator argument is used)

CompareTo comparison is based on the Unicode value of each character in the strings.

The result is a negative integer if this String object lexicographically precedes the argument string.
The result is a positive integer if this String object lexicographically follows the argument string.
The result is zero if the strings are equal; compareTo returns 0 exactly when the equals(Object) method would return true.

lexicographic ordering: If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both.

Why the 'two argument' version of this method doesn't work here and gives unpredictable output?

Arrays.binarySearch is producing the right results. I do not see any un-expected results.
sa has sa[0] = four, sa[1] = one, sa[2] = three, sa[3]= two and for overloaded binarySearch method right output is produced.

[Astha Sharma]

Thanks Anayonkar Shivalkar and Zeeshan Sheikh for the explanation.
I was not considering that it's "Binary Search". It would not need the Comparator as argument it it would be method performing linear search and I was thinking of it as lenier search algorithm, thats why got confused. My mistake