Algorithm 19 : binarySearch
설명
- 오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
예시
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
생각
이진탐색 알고리즘 O(logN)을 사용해 풀어야 하므로 배열을 계속 반으로 쪼개며 생각해야 겠다.
풀이
const binarySearch = function (arr, target) {
let left = 0,
right = arr.length - 1;
while (left <= right) {
let middle = parseInt((right + left) / 2);
if (arr[middle] === target) {
return middle;
}
if (target < arr[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
};
깨달은 점
이진탐색방법에 대한 레퍼런스를 참고해서 문제를 풀었다.
가운데를 기점으로 값이 큰지 작은지를 판단하는 것이 반복문을 통해 요소 하나씩 탐색하는 것보다 효율적이라는 게 감이 왔다.
그리고 left, right 변수를 세워서 while문으로 조절하는 방법이 생소했는데 이번문제를 기회로 반복해서 풀면서 익숙해져야겠다.
Author And Source
이 문제에 관하여(Algorithm 19 : binarySearch), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@boo1996/Algorithm-19-binarySearch저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)