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.

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.

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 ʻequals`method returns true, and when the`

compareTo` method returns non-zero, the ʻequals`

method returns false". It would be good to do so.

static

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.

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