java.util.ArraysクラスにbinarySearchメソッドは実装されていますが、「keyで指定された要素を複数持つ場合にはどれが返されるか保証されていない」という使い道に困り果てそうな実装であるため、自前でライブラリを持っておくべきかと思われます
※2023/09/22追記およびコード修正：型パラメータを使用して汎用性を持たせました（配列で書くことも不可能ではありませんが、T[]型を引数として渡すようにするとプリミティブ型配列を引数として与えた時にコンパイルエラーとなり、ラッパークラス型配列を渡さなければ正常実行が不可能であるのみならず、プリミティブ型配列を引数とするArrays#sortは改良版のクイックソートにより実装されており、最悪n^2に比例する実行時間を要してTLEする可能性を孕んでいるため、各データをプリミティブ型で保存する意思を最初から捨ててマージソートにより実装された並べ替え処理を確実に呼び出すためにリストで実装する方が良いと判断しました）
import java.util.List;
public final class BinarySearcher {
/**
* 昇順ソート済みのリストに対して二分探索を実行し、
* key <= list.get(index)
* となるような最小のindexを返す
* @param <T> リストの各要素の型
* @param list 探索対象のリスト
* @param key 探索キー
* @return 適切な要素が存在する場合は最小のインデックス、存在しない場合は-1
*/
public static <T extends Comparable<T>> int findSmallestIndexGreaterThanOrEqualToKey(List<T> list, T key) {
return findSmallestIndexGeneral(list, key, true);
}
/**
* 昇順ソート済みのリストに対して二分探索を実行し、
* key < list.get(index)
* となるような最小のindexを返す
* @param <T> リストの各要素の型
* @param list 探索対象のリスト
* @param key 探索キー
* @return 適切な要素が存在する場合は最小のインデックス、存在しない場合は-1
*/
public static <T extends Comparable<T>> int findSmallestIndexGreaterThanKey(List<T> list, T key) {
return findSmallestIndexGeneral(list, key, false);
}
/**
* 昇順ソート済みのリストに対して二分探索を実行し、
* list.get(index) <= key
* となるような最大のindexを返す
* @param <T> リストの各要素の型
* @param list 探索対象のリスト
* @param key 探索キー
* @return 適切な要素が存在する場合は最大のインデックス、存在しない場合は-1
*/
public static <T extends Comparable<T>> int findLargestIndexLessThanOrEqualToKey(List<T> list, T key) {
return findLargestIndexGeneral(list, key, true);
}
/**
* 昇順ソート済みのリストに対して二分探索を実行し、
* list.get(index) < key
* となるような最大のindexを返す
* @param <T> リストの各要素の型
* @param list 探索対象のリスト
* @param key 探索キー
* @return 適切な要素が存在する場合は最大のインデックス、存在しない場合は-1
*/
public static <T extends Comparable<T>> int findLargestIndexLessThanKey(List<T> list, T key) {
return findLargestIndexGeneral(list, key, false);
}
private static <T extends Comparable<T>> int findSmallestIndexGeneral(List<T> list, T key, boolean isInclusive) {
int left = -1, right = list.size();
while (right - left > 1) {
int mid = (left + right) / 2;
if (isInclusive ? key.compareTo(list.get(mid)) <= 0 : key.compareTo(list.get(mid)) < 0) {
right = mid;
} else {
left = mid;
}
}
return right == list.size() ? -1 : right;
}
private static <T extends Comparable<T>> int findLargestIndexGeneral(List<T> list, T key, boolean isInclusive) {
int left = -1, right = list.size();
while (right - left > 1) {
int mid = (left + right) / 2;
if (isInclusive ? list.get(mid).compareTo(key) <= 0 : list.get(mid).compareTo(key) < 0) {
left = mid;
} else {
right = mid;
}
}
return left;
}
}
