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

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.

Recommended Posts

Write a class that can be ordered in Java
Write a class in Kotlin and call it in Java
Create a jar file that can be executed in Gradle
Java (super beginner edition) that can be understood in 180 seconds
[MQTT / Java] Implemented a class that does MQTT Pub / Sub in Java
What is a class in Java language (3 /?)
Summary of ORM "uroboroSQL" that can be used in enterprise Java
What is a class in Java language (1 /?)
What is a class in Java language (2 /?)
Creating a matrix class in Java Part 1
How to make a key pair of ecdsa in a format that can be read by Java
I made a class that can use JUMAN and KNP from Java
[Android Studio] Description that can be continuously input in SQLite Database [Java]
[Java] Implement a function that uses a class implemented in the Builder pattern
GetInstance () from a @Singleton class in Groovy from Java
A bat file that uses Java in windows
A quick review of Java learned in class
General-purpose StringConverter class that utilizes generics in Java8
[Java 8] Until converting standard input that can be used in coding tests into a list or array
Log out a CSV file that can be read in Excel using logback
Technology excerpt that can be used for creating EC sites in Java training
Basic functional interface that can be understood in 3 minutes
A quick review of Java learned in class part4
A quick review of Java learned in class part3
A quick review of Java learned in class part2
Convenient shortcut keys that can be used in Eclipse
A library that realizes multi-line strings in Java multiline-string
Write class inheritance in Ruby
Write flyway callbacks in Java
Programming can be a god.
Find a subset in Java
Write Java8-like code in Java8
List of devices that can be previewed in Swift UI
Problems that can easily be mistaken for Java and JavaScript
Introduction to Rakefile that can be done in about 10 minutes
Find a Switch statement that can be converted to a Switch expression
Java 14 new features that could be used to write code
Syntax and exception occurrence conditions that can be used when comparing with null in Java
[Java 8] Sorting method in alphabetical order and string length order that can be used in coding tests
Static analysis tool that can be used on GitHub [Java version]
3 Implement a simple interpreter in Java
I can't create a Java class with a specific name in IntelliJ
Object-oriented design that can be used when you want to return a response in form format
How to implement a job that uses Java API in JobScheduler
Handle business logic for a set of Entity in Java class
Note that system properties including JAXBContext cannot be used in Java11
I wrote a Stalin sort that feels like a mess in Java
StringBuffer and StringBuilder Class in Java
I made a question that can be used for a technical interview
A simple sample callback in Java
SwiftUI View that can be used in combination with other frameworks
Creating a matrix class in Java Part 2-About matrices (linear algebra)-
It seems that data class-like functions will be added in Java14
Let's touch on Deep Java Library (DJL), a library that can handle Deep Learning in Java released from AWS.
Mecab installation that can be done almost by typing a command
Get stuck in a Java primer
Introduction to Java that can be understood even with Krillin (Part 1)
How to override in a model unit test so that Faker can be used to generate random values
How do you write in Scala that was written in Java? (List → Map)
How to test a private method in Java and partially mock that method
[Java] Introducing "ZT Zip", a utility that can handle ZIP files very easily