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;
};

キーワード

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