100日アルゴリズム[16日目・バイナリサーチ]

解いた問題

https://leetcode.com/problems/binary-search/

解法

通常のバイナリサーチの考え方に基づきtypescriptで実装した。

function search(nums: number[], target: number): number {
    let left = 0;
    let right = nums.length -1;
    while (left <= right) {
        const middle = Math.floor((left + right) / 2);
        if (target == nums[middle]) {
          return middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            right = middle -1;
        }
    }
    return -1;
};

バイナリサーチとは？

バイナリサーチでは、ソート済みの配列が与えられその配列から特定の値(value)を効率的に探す。配列の一番左と一番右にまず点を取り、その2点の中央の値をまず調べ、中央の値が探している特定の値と同じかそれか、探している値より小さいか大きいかをまず調べる。もし中央の値が特定の値より小さければ一番右側の点を最初の中央の値よりさらに1個進んだインデックス位置のところまで持ってくる。もし中央の値が特定の値より大きければ一番左側の点を最初の中央の値のインデックス位置より1つ手前のところまで持ってくる。このようにして探している特定の値を効率よく探せるアルゴリズム。もし探している値がなければ-1を返す。

補足

上記再帰関数を使っても書ける。