토이 10번

야 나 개 ·2021년 11월 29일
0

주간 문제아이돌 

목록 보기
12/17
post-thumbnail

문제

오름차순 정렬된 정수의 배열(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;
};
profile
야 나도 개발자 될 수 있어

0개의 댓글