バイナリサーチ

数値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に戻ってください.

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

Solution

最初は問題が簡単だと思っていました.配列のlengthを半分にして左、右をチェックし、再び配列をsliceに切り取り、中間値でアクセスしますが、value値が見つかってもindex値は見つかりません.急に問題が難しくなったような気がします.
線形探索ならすぐに終わるはずですが、いずれにしてもバイナリ探索問題なので、再度問題を見ながら考えます.繰返しが可能な瞬間を考えると,鄭敏は数値解釈の二分法を例に,近接法を提案した.もちろん、並べ替えは連続したグラフではありませんが、完全にヒントを得ることができます.次に,中間値を左右に移動する方法で実現する.
二分法の解法

aとbの中間値は紡績方式の年に最も近い.(a+b)/2
バイナリナビゲーションの方法

Solution Code

const findIndex = (nums, target) => {
  let left = 0
  let right = nums.length -1
  
  while(left < right){
    let middle = Math.round((left+right)/2)
    
    if( nums[middle] === target) {
      return middle
    }
    else if(nums[middle] < target) {
      left = middle + 1
    } else if(nums[middle] > target){
      right = middle - 1
    }
  } 
  if(left === right) {
    return right // return left
  }
  return -1
}

左と右が出会うまで繰り返し、中間値を求めます.

中間値を求めると、目標値と比較します.

ターゲット値が中間値に等しい場合は、すぐに戻ります.

ターゲットの値が大きい場合は、左側が中間値の+1(left=medial+1)

ターゲットの値が小さい場合は、右側に中間値-1(right=medial-1)を挿入します.

また,最後まで繰り返すと,左と右が出会うと,どの値を選択してもターゲット値のインデックス値となる.

この問題は今までCode Kataの中で一番面白かったようです.本当に簡単で難しかったし、また問題に近づいたとき、数学で考えているような気がします.