Search and equals()

There are five static search-related methods in the class Collections:

int binarySearch(List<Comparable<T>> list, T key)
int binarySearch(List<T> list, T key, Comparator<T> comparator)
int indexOfSubList(List<?> source, List<?> target)
int lastIndexOfSubList(List<?> source, List<?> target)
int frequency(Collection<?> collection, Object object)

The binarySearch() methods search for the key value in the provided list. The important thing to notice is that the provided list must be sorted in ascending order because of the nature of the binary search. The algorithm compares the key to the middle element of the list; if they are unequal, the half in which the key cannot belong is ignored and the algorithm compares the key to the middle element of the other half of the list. The search continues until the element equal to the key is found or only one element is left to search and it is not equal to the key.

The indexOfSubList() and lastIndexOfSubList() methods return the position of the provided sublist in the provided list:

List<String> list1 = List.of("s3","s5","s4","s1");
List<String> list2 = List.of("s4","s5");
int index = Collections.indexOfSubList(list1, list2);
System.out.println(index);  //prints: -1

List<String> list3 = List.of("s5","s4");
index = Collections.indexOfSubList(list1, list3);
System.out.println(index);   //prints: 1

Please notice that the sublist should be exactly in the same order. Otherwise, it will not be found.

And the last method, frequency(Collection, Object), returns the number of times the provided object appears in the provided collection:

List<String> list4 = List.of("s3","s4","s4","s1");
int count = Collections.frequency(list4, "s4");
System.out.println(count);         //prints: 2

If you are going to use these methods (or any other methods that search collections for that matter) and if the collections include objects of custom classes, you have to have the method equals() implemented. A typical search algorithm uses the method equals() for the identification of the object. If you do not implement the method equals() in your custom class, the method equals() from the base class Object is going to be used, which compares only the object references, not their states (values of their fields). Here is a demonstration of this behavior:

class A{}
class B extends A{}

List<A> list5 = List.of(new A(), new B());
int c = Collections.frequency(list5, new A());
System.out.println(c);         //prints: 0

A a = new A();
List<A> list6 = List.of(a, new B());
c = Collections.frequency(list6, a);
System.out.println(c);         //prints: 1

As you can see, the object of class A is found only if it is literally the same object. But if we implement the method equals(), then the object of class A is found according to the criteria we have put in the method equals() implementation:

class A{
    @Override
    public boolean equals(Object o){
        if (o == null) return false;
        return (o instanceof A);
    }
}
class B extends A{}

List<A> list5 = List.of(new A(), new B());
int c = Collections.frequency(list5, new A());
System.out.println(c);         //prints: 2

A a = new A();
List<A> list6 = List.of(a, new B());
c = Collections.frequency(list6, a);
System.out.println(c);         //prints: 2

Now, the count of objects A in each case is 2 because B extends A and thus has two types, B and A.

If we prefer to identify the object by exactly the current class name and not include its parent class in the consideration, we should implement the method equals() differently:

class A{
    @Override
    public boolean equals(Object o){
        if (o == null) return false;
        return o.getClass().equals(this.getClass());
    }
}
class B extends A{}

List<A> list5 = List.of(new A(), new B());
int c = Collections.frequency(list5, new A());
System.out.println(c);         //prints: 1

A a = new A();
List<A> list6 = List.of(a, new B());
c = Collections.frequency(list6, a);
System.out.println(c);         //prints: 1

The method getClass() returns the class name used when the object was created by the operator new. That is why the count in both cases is now 1.

For the rest of this chapter, we are going to assume that the method equals() is implemented in the elements of the collections and arrays. Most of the time, we are going to use objects of the class String in our example. As we have mentioned earlier in Chapter 9, Operators, Expressions, and Statements, the class String has an equals() method implementation based on the string literal value, not on object reference only. And, as we have explained in the previous subsection, the class String also implements the interface Comparable so that it provides natural ordering.