오름차순 정렬된 정수의 배열(arr)과 정수(target)를 입력받아 target의 인덱스를 리턴해야 합니다.
이진탐색 알고리즘(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
const binarySearch = function (arr, target) {
// TODO : 여기에 코드를 작성합니다.
// 이진트리 방법으로 사용한다.
// 이분검색의 전제조건은 오름차순 정렬이 되어 있어야 한다. (물론 내림차순도 된다)
// 배열의 중간을 짜르고 또 짜르면 logN이 된다.
let result = -1
let lt = 0, rt = arr.length -1;
while (lt <= rt){
let mid = parseInt((lt + rt) / 2);
if(arr[mid] === target){
result = mid;
break;
}
else if (arr[mid] > target){
rt = mid - 1
} else {
lt = mid + 1;
}
}
return result;
};