[Toy] binarySearch
6575 ワード
10_binarySearch
質問する
昇順整数の配列(arr)と整数(target)を入力してtargetのインデックスを返す必要があります.
入力
パラメータ1:arr
パラメータ2:target
しゅつりょく
注意事項
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;
};
キーワード
Reference
この問題について([Toy] binarySearch), 我々は、より多くの情報をここで見つけました https://velog.io/@ge5rg2/Toy-binarySearchテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol