AtCoder 鉄則本 B11 解法メモ Kotlinで超簡易版lower_bound, upper_bound

一応準備しておこうかと思って試作。あまりちゃんと分かってないので詳細理解は追って・・・

解いていた問題

解法メモ

二分探索する
- Kotlin(Java)のbinarySearchではリスト内に同値がある場合に返る値が保証されない*1 *2ため、lower_boundのように利用できない
- ので次回以降に備えて作っちゃおう
  - C++の実装*3 *4を参考にしようと思ったけど、読めなかった・・・し、今の時点でそこまで汎用性高いのいらないかも
  - 同じ方向性でC#で実装している方がいらっしゃった*5のでC#のコードを参考にしながら実装してみる

実装メモ

一旦↓の感じになった

    /**
     * ref: https://webbibouroku.com/Blog/Article/cs-lowerbound-upperbound
     */
    fun lowerBound(list: List<Int>, value: Int): Int {
        var left = 0
        var right = list.lastIndex
        while (left <= right) {
            val mid = (left + right) / 2
            if (list[mid] < value) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return left
    }

    /**
     * ref: https://webbibouroku.com/Blog/Article/cs-lowerbound-upperbound
     */
    fun upperBound(list: List<Int>, value: Int): Int {
        var left = 0
        var right = list.lastIndex
        while (left <= right) {
            val mid = (left + right) / 2
            if (list[mid] <= value) {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return left
    }

ざっとですが、参考にさせていただいた記事でテストしていたin/outが想定通り出るところまではテスト済み

    @Test
    fun lowerBoundTest() {
        val list = mutableListOf(1, 2, 2, 2, 4, 4, 4, 5, 6)
        val expected = mutableListOf(0, 0, 1, 4, 4, 7, 8, 9)

        for (i in 0..7) {
            assertEquals(expected[i], _library().lowerBound(list, i))
        }
    }

    @Test
    fun upperBoundTest() {
        val list = mutableListOf(1, 2, 2, 2, 4, 4, 4, 5, 6)
        val expected = mutableListOf(0, 1, 4, 4, 7, 8, 9, 9)

        for (i in 0..7) {
            assertEquals(expected[i], _library().upperBound(list, i))
        }
    }