Introduction

From the book "Algorithms and Data Structures Learned in New and Clear Java" Chapter 3-3 Binary Search, there was a standard to remember when writing Java, so I will summarize it in this article including binary search. It was.

Binary search with Java

Java provides a standard library of methods for binary search from arrays. A binarySearch method that belongs to the java.util.Arrays class.

Reference: https://docs.oracle.com/javase/jp/8/docs/api/java/util/Arrays.html

As you can see in the reference link above, many binarySearch methods are defined to support various element types. Both binary search for key value elements in an array sorted in ascending order (results are undefined if not sorted in ascending order). If there is a search key in the array, the index of the search key is returned, and if it does not exist, double (-(insertion point) -1) is returned.

This time, we will focus on the following two points.

static int binarySearch(Object[] a, Object key)
static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)

static int binarySearch(Object[] a, Object key) Judge the magnitude relationship of elements in a natural order. Please refer to the following for natural ordering.

Reference: https://docs.oracle.com/javase/jp/8/docs/api/java/lang/Comparable.html

If you have an array of types that implements the Comparable interface in the reference link above, you can easily write code for binary search using this method.

A little standard of class definition that can be ordered naturally

In other words, even for your own class, you can define natural ordering by implementing this Comparable interface, and you can use this method. It's a good idea to remember the following as a little standard.

`Naturally ordered class.java`


public class Hoge implements Comparable<Hoge> {
    //Fields, methods, etc.

    @Override
    public int compareTo(A c) {
        //A positive value if this is greater than c,
        //Negative value if this is less than c,
        //Returns 0 if this is equal to c.
    }

    @Override
    public boolean equals(Object c) {
        //True if this is equal to c,
        //Returns false if this is not equal to c.
    }
}

At this time, consistency can be obtained such as "when the conpareTo method returns 0, the ʻequalsmethod returns true, and when thecompareTo method returns non-zero, the ʻequals method returns false". It would be good to do so.

static int binarySearch(T[] a, T key, Comparator<? super T> c) This method can be used for a binary search from an array that is ** not ** ordered in its natural order. Since it is a generic method, any element of the array is OK.

However, you must tell the method how to determine the magnitude relationship of each element. To do this, pass an instance of the class that implements the java.util.Comparator interface as the third argument.

A little formula that defines a comparator

For example, a class Fuga comparator can be defined as: It's a good idea to remember this as a little standard.

`Define a comparator inside the class.java`


public class Fuga {
    //Fields, methods, etc.

    public static final Comparator<Fuga> COMPARATOR = new Comp();

    private static class Comp implements Comparator<Fuga> {
        public int compare(Fuga d1, Fuga d2) {
            //If d1 is greater than d2, then a positive value,
            //Negative value if d1 is less than d2,
            //Returns 0 if d1 is equal to d2.
        }
    }
}

By passing Fuga.COMPARATOR as the third argument of the binarySearch method, the magnitude relation can be determined based on the defined comparator and a binary search of the Fuga type array can be performed.

[GO] Write a class that can be ordered in Java