javaでCの[lower_bound関数]や[upper_bound関数]を使いたい

C のlower_bound関数や upper_bound関数はjavaにないのか？

【結論】

• そのものズバリの関数は存在しない
• ただし、Arrays#binarySearch()を使えば可能
  • やり方は二通り
    • comparatorを実装する
    • Arrays#binarySearch()に渡す引数を操作する

【実装】

• Comparatorを実装する

  • 【参考】のリンク先に丁寧な解説があるので其方で

• Arrays#binarySearch()に渡す引数を操作する

  • binarySearch(Object[] a, Object key)　の keyを $\pm0.1$ （影響が出ない桁数で $\pm$ ）する

サンプル出力用ソース*

	private void hoge() {
		final int CONST_LOOP = 10;
		double[] sampleArray = { -1d, 0d, 1d, 1d, 3d, 3d, 5d, 5d, 6d, 7d };
		System.out.println("normal");
		System.out.println("xs: " + Arrays.toString(sampleArray));

		for (int index = 0; index <= CONST_LOOP; ++index) {
			long result = Arrays.binarySearch(sampleArray, index);
			long insertionPoint = (result >= 0) ? result : ~result;
			System.out.printf("index: %d | result: %2d | the position where value can be inserted: %d\n", index, result, insertionPoint);
		}
		System.out.println("upper");
		System.out.println("xs: " + Arrays.toString(sampleArray));

		for (int index = 0; index <= CONST_LOOP; ++index) {
			long result = Arrays.binarySearch(sampleArray, index + 0.1);
			long insertionPoint = (result >= 0) ? result : ~result;
			System.out.printf("index: %d | result: %2d | the position where value can be inserted: %d\n", index, result, insertionPoint);
		}

		System.out.println("lower");
		System.out.println("xs: " + Arrays.toString(sampleArray));

		for (int index = 0; index <= CONST_LOOP; ++index) {
			long result = Arrays.binarySearch(sampleArray, index - 0.1);
			long insertionPoint = (result >= 0) ? result : ~result;
			System.out.printf("index: %d | result: %2d | the position where value can be inserted: %d\n", index, result, insertionPoint);
		}
	}

実行結果
normal(引数加工無し)
Search対象の配列 $ [-1.0,\quad 0.0,\quad 1.0,\quad 1.0,\quad 3.0,\quad 3.0,\quad 5.0,\quad 5.0,\quad 6.0,\quad 7.0]$

|挿入したい数値|生のresult|否定して得られる挿入位置|
|:-:|:-:|:-:|:-:|
|0 | 1 |1|
|1 | 2 |2|
|2 | -5 |4|
|3 | 4 |4|
|4 | -7 |6|
|5 | 7 |7|
|6 | 8 |8|
|7 | 9 |9|
|8 | -11 |10|
|9 | -11 |10|
|10 | -11 |10|

upper_bound(引数を+0.1)
Search対象の配列 $ [-1.0,\quad 0.0,\quad 1.0,\quad 1.0,\quad 3.0,\quad 3.0,\quad 5.0,\quad 5.0,\quad 6.0,\quad 7.0]$

|挿入したい数値|生のresult|否定して得られる挿入位置|
|:-:|:-:|:-:|:-:|
|0 | -3 |2|
|1 | -5 |4|
|2 | -5 |4|
|3 | -7 |6|
|4 | -7 |6|
|5 | -9 |8|
|6 | -10 |9|
|7 | -11 |10|
|8 | -11 |10|
|9 | -11 |10|
|10 | -11 |10|

lower_bound(引数を-0.1)
Search対象の配列 $ [-1.0,\quad 0.0,\quad 1.0,\quad 1.0,\quad 3.0,\quad 3.0,\quad 5.0,\quad 5.0,\quad 6.0,\quad 7.0]$

|挿入したい数値|生のresult|否定して得られる挿入位置|
|:-:|:-:|:-:|:-:|
|0 |-2 |1|
|1 | -3 |2|
|2 | -5 |4|
|3 | -5 |4|
|4 | -7 |6|
|5 | -7 |6|
|6 | -9 |8|
|7 | -10 |9|
|8 | -11 |10|
|9 | -11 |10|
|10 | -11 |10|

【参考】

java.util.Arrays.binarySearch で二分探索 + Java で std::lower_bound/upper_bound