2分探索

配列をつかって該当の数字があるか見つける

step1. 関数を定義する。引数として、配列と該当の数値を渡す。
step2. 配列の最初を0とし、配列の最後をn-1番目とする
step3. n-1番目が大きい間は繰り返す処理にする
step4. 中央値を探す処理を記述
step5. もし、該当の値と中央値が一緒ならそこで処理を終了
step6. それ以外で、もし、該当の数値が中央値より大きい場合は右側を探す
step7. それ以外で、もし、該当の数値が中央値より小さい場合は左側を探す

// 二分探索の実装

const nums = [1,5,8,2,4,9,10];

//特定の数字は配列の中にあるか確認する

//step1. 関数を定義する。引数として、配列と該当の数値を渡す。
//step2 配列をソート済みにする
//step3. 配列の最初を0とし、配列の最後をn-1番目とする
//step4. n-1番目が大きい間は繰り返す処理にする
//step5. 中央値を探す処理を記述
//step6. もし、該当値が配列の中にある場合はIncludeと表示
//step7. それ以外で、もし、該当の数値が中央値より大きい場合は右側を探す
//step8. それ以外で、もし、該当の数値が中央値より小さい場合は左側を探す

//step1
function binary_search(arr,target){
    //step2
    const sortedArr = [...arr].sort((a, b) => a - b);
    //step3
    let first = 0;
    let last = sortedArr.length - 1;

    //step4
    while(first <= last){
        //step5
        const mid = Math.floor((first + last)/2);
        //step6
        if(sortedArr[mid] === target){
            return "Include";
        }else{
            //step7, step8
            if(sortedArr[mid] < target){
                first = mid + 1;
            }else{
                last = mid - 1;
            }
        }
    }
    return "Not include";
}


console.log(binary_search(nums,5));