-
Section3 Daily Coding 14_binarySearch공부/데일리코딩 2022. 7. 12. 09:34반응형
문제
오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
입력
인자 1 : arr
- number 타입을 요소로 갖는 배열
- arr[i]는 정수
인자 2 : target
- number 타입의 정수
출력
- number 타입을 리턴해야 합니다.
주의사항
- 이진탐색 알고리즘(O(logN))을 사용해야 합니다.
- 단순한 배열 순회(O(N))로는 통과할 수 없는 테스트 케이스가 존재합니다.
- target이 없는 경우, -1을 리턴해야 합니다.
입출력 예시
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
Reference Code
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; };
반응형'공부 > 데일리코딩' 카테고리의 다른 글
Section3 Daily Coding 16_insertionSort (0) 2022.07.14 Section3 Daily Coding 15_powerSet (2) 2022.07.13 Section3 Daily Coding 13_orderOfPresentation (0) 2022.07.11 Section3 Daily Coding 10_balancedBrackets (0) 2022.07.09 Section3 Daily Coding 11_getItemFromTwoSortedArrays (0) 2022.07.09