Algorithm - CodeKata #20 📌

1.バイナリサーチ

バイナリナビゲーションを学ぶ前に、「リニアサーチ」(Linear Search)を見てみましょう.
**線形ナビゲーションまたはバイナリナビゲーションの要素は、適用できるアルゴリズムを昇順または降順に並べなければなりません.let arr = [2, 4, 6, 8, 11, 14];上の配列で要素を8として検索するにはどうすればいいですか?
index 0から5まで要素を順番にチェックし、8が現れるまでfor文を回します.
最初のインデックスから1つずつ検索することをリニアナビゲーションと呼びます.
しかし、配列の長さが1000であり、1000という要素を検索する必要があり、arr[9999]に1000が偽設されている場合、for文は何回返されるのでしょうか.
はい、1000番です.
線形ナビゲーションの欠点は、要素に基づいて複数回ナビゲーションする必要があることです.
つまり、1を探す場合はfor文を1回だけ回転させることができますが、1000を検索する場合はfor文を1000回回転させる必要があります.
for文の内部に複雑な計算が含まれている場合、実行速度が遅くなり、効率が低下します.
では、もっと効果的なアルゴリズムはありますか?
はい.これがバイナリナビゲーションです.
バイナリ・ナビゲーションは、順番に検索するのではなく、真ん中から検索します.
次の配列で7を検索する必要がある場合は、
まず、中間位置の要素(7<14)を比較し、検索する値より大きい場合は左側の中間で再比較します.
サイズを再比較して右から中、左から中、再配置するナビゲーション方法をダブルナビゲーションと呼びます.

2. Question

数値nums配列の昇順と検索するtargetをパラメータとすると、
targetはいくつかのindexです.戻ってください.

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
설명: 찾지 못하면 -1로 return 해주세요.

nums配列の要素には重複する値はありません.

3. Answer

const nums = [-1,0,3,5,9,12];
const target = 9;

const search = (nums, target) => {
    let low = 0
    let high = nums.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (nums[mid] < target) {
            low = mid + 1
        } else if (nums[mid] > target) {
            high = mid - 1
        } else {
            return mid
        }
    }
    return -1
}

search(nums, target); // 4