ソートされた配列から対象となる数値の範囲を取得する

問題

ソートされた重複のある配列が与えらる。この配列から対象となる数値の最初から最後までの配列のインデックスを返しなさい。
対象の数値がない場合は-1を返す

Input: A = [1,3,3,5,7,8,9,9,9,15], target = 9
Output: [6,8]

Input: A = [100, 150, 150, 153], target = 150
Output: [1,2]

Input: A = [1,2,3,4,5,6,10], target = 9
Output: [-1, -1]

.
.
.
.
.
.
.
.
.
.
.
.

回答

JavaScriptで回答する。
普通に配列の最初から探索すると計算量O(N)で範囲を取得できる。

が今回の場合はソート済みの配列が与えられるためもう少し効率の良い方法が考えられる。バイナリサーチだとO(logN)で計算できるので、バイナリサーチを使ったほうが良さそう。
対象の要素を見つけたらそこから範囲を絞れば良い。

function getRange(nums, target) {
    let left = 0
    let right = nums.length - 1

    while (left <= right) {
        const center = Math.floor((right + left) / 2)
        if(nums[center] === target) {
            let start = center
            let end = center
            while(nums[center] == nums[start]) {
                start -= 1
            }
            while(nums[center] == nums[end]) {
                end += 1
            }
            return [start + 1, end - 1]
        } else if (nums[center] < target) {
            left = center + 1
        } else {
            right = center - 1
        }

    }

    return -1
}

ということで単なるバイナリサーチの応用だった

計算量: O(logN)
メモリ: O(1)