[Toy] binarySearch


10_binarySearch


質問する


昇順整数の配列(arr)と整数(target)を入力してtargetのインデックスを返す必要があります.

入力


パラメータ1:arr

  • 番号タイプ要素の配列
  • arr[i]は整数
  • である.

    パラメータ2:target

  • 番号タイプの整数
  • しゅつりょく

  • numberタイプを返さなければなりません.
  • 注意事項

  • バイナリナビゲーションアルゴリズム(O(logn))を使用する必要があります.
  • には、単純な配列順序(O(N))に合格できないテストケースがある.
  • targetがない場合は、-1を返さなければなりません.
  • I/O例

    let output = binarySearch([0, 1, 2, 3, 4, 5, 6], 2);
    console.log(output); // --> 2
    
    output = binarySearch([4, 5, 6, 9], 100);
    console.log(output); // --> -1

    首都コード

    arr의 배열을 left, right로 분리하고 middle값을 찾은 다음
    target과 비교해서 target이 더 크다면 right를 arr로 대체해서 다시 콜백 -> 비교
    이러한 진행을 반복해서 값이 있는지 확인하고 더 이상 진행할 수 없다면 (while문 사용) return -1을 한다.

    Code

    //[0, 1, 2, 3, 4, 5, 6] target=2로 예시
    const binarySearch = function (arr, target) {
      let left = 0, right = arr.length-1; // right=6
      while(left <= right){
        // mid=3 > mid=1 > mid=2
      	let mid = Math.round((left+right)/2)
        if(arr[mid] === target){
        	return mid
        }
        if(target < arr[mid]) {
          // right = 2
        	right = mid -1;
        } else {
          // left=1
        	left = mid + 1;
        }
      }
      return -1;
    };

    キーワード

  • バイナリナビゲーションアルゴリズム