BinarySearch

[Abhi vijay]

Source: K&B

 import java.util.*;
public class Geo
{
public static void main(String[] args)
{
String[] s ={"map","pen","marble"};
Othello o = new Othello();
Arrays.sort(s,o);
for(String s2:s)
System.out.println(s2+" ");
System.out.println(Arrays.binarySearch(s,"pen"));  // Line1 
}
static class Othello implements Comparator<String>
{
public int compare(String a , String b)
{
return b.compareTo(a);
}
}
}   

Line 1 is printing -4, but shouldnt it be -3??

[Ankit Garg]

No, -4 is correct (Hint: we didn't use comparator while searching)...

[Punit Singh]

It is undefined behavior here, so you cannot say anything here.

[Abhi vijay]

Ankit Garg wrote:No, -4 is correct (Hint: we didn't use comparator while searching)...

Yes, I know we havent used Comparator. But then how is it calculating the insertion point??? :?:

[Punit Singh]

 public class Geo  
{  
	public static void main(String[] args)  
	{  
		String[] s ={"map","pen","marble"};  
		Othello o = new Othello();  
		Arrays.sort(s,o);  
		for(String s2:s)  
			System.out.println(s2+" ");  
		System.out.println(Arrays.binarySearch(s,"abhi",o));  // Line1
		System.out.println(Arrays.binarySearch(s,"vaja",o));  // Line1
	
	}  
	static class Othello implements Comparator<String>  
	{  
		public int compare(String a , String b)  
		{  
			return b.compareTo(a);  
		}  
	}  
}   

If you want calculation index, then run this.

[Ankit Garg]

As punit said, and as the documentation says, the result is undefined. Actually it uses binary search algorithm i.e. breaking the array into half and then matching the element, so it will first match pen with the middle element i.e. marble in this case. Since it will find pen to be greater than marble, so it will move forward and break the remaining array into half but since there is only one element so it will match pen with the last element i.e. map and will find it even greater than that so it will think that pen must be the last element i.e. 4th element or element at index 3. So it will return - (index + 1) i.e. - (3 + 1) i.e. -4...

[Abhi vijay]

Thanks, But I know how to calculate insertion point when comparator is used. But didnt know how it is done without comparator. I think Ankit has explained it.

[Ankit Garg]

Abhi vijay wrote:Thanks, But I know how to calculate insertion point when comparator is used. But didnt know how it is done without comparator. I think Ankit has explained it.

It is not about comparator. I just explained the binary search algorithm here and how in this case it will lead to wrong result since we didn't use the comparator while searching . The binary search algorithm is the same whether you use comparator or not...

[Yuan Du]

Hi everyone,

This is from KB book page 558
When solving searching and sorting questions, two big gotchas are:
1. Searching an array or collection that hasn’t been sorted.
2. Using a Comparator in either the sort or the search,
but not both

I don't understand the second point, why we can't use a comparator for sorting and searing.

Thank you very much!

Yuan

[Punit Singh]

Second point is saying, if you sort a list using Comparator, then you must search that list using Comparator by passing Comparator as third argument to binarySearch(), otherwise result will be undefined.

[Yuan Du]

Ok Punit.
You mean i should use the method "public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)",
but i can not code it in two statements
like

 
Object[] a = new Object[5];
Arrays.sort(a, new MyComparator());
Arrays.binarySearch(a, new MyComparator());

because the sequence of the object[] won't be changed after the first statement, am i right?

Thank you!

Yuan

[Punit Singh]

Arrays.binarySearch(a, new MyComparator());

What are you searching here?

[Yuan Du]

oh, sorry, i meant one element of object array 'a'.

eg.Arrays.binarySearch(a, a[0]);

[Punit Singh]

If you have use new MyComparator() is sorting:

Arrays.sort(a, new MyComparator()); 

then you must use new MyComparator() is searching also,

Arrays.binarySearch(a,whateverData, new MyComparator());

Otherwise you will get answer undefined. It may happen MyComparator sorted data in reverse order, and you did not pass MyComparator in binarySearch, then binarySearch will search data in natural order instead of reverse order and you will get undefined result.

[Yuan Du]

Ok, thank you Punit.
I got it.


Yuan