JavaScript Algorithm - binarySearch

문제설명: 

간단하게 풀이하면 이진탐색 구현 문제이다. 대신에 알고리즘 복잡도를 O(logN)이 되도록 구현해야한다.
그렇다면 이진탐색이란 무엇인가?? 다음 링크를 찾아보면 된다. 이진탐색이란 말 그대로 오름차순으로 정렬된 정수의 리스트를 두 부분 리스트로 나눠서 오른쪽, 왼쪽에서 탐색하여 찾고자하는 값을 찾는 알고리즘이다. 

입력

인자 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

 

 

풀이 1 : 처음에 이 방식으로 풀면 될 줄 알았으나 효율성 측면에서 문제가 있는지 테스트 통과가 되지 않았다.

const binarySearch = function (arr, target) {
  let count = 0;
  let testArr = [...arr];
  //console.log("testArr", testArr);
  //   let front = testArr.slice(0, testArr.length / 2);
  //   let rear = testArr.slice(testArr.length / 2);
  //   console.log(front, rear);

  //testArr의 길이가 1 초과일 때
  while (testArr.length > 1) {
    //[0,1,2,3,4,5,6]이면
    //front = [0, 1, 2], rear=[3, 4, 5, 6]
    let front = testArr.slice(0, testArr.length / 2);
    let rear = testArr.slice(testArr.length / 2);
    if (front[front.length - 1] >= target) {
      testArr = front;
    } else if (rear[0] <= target) {
      testArr = rear;
      count += front.length;
    } else {
      testArr = [];
    }
  }
  //console.log("testarr", testArr);
  if (testArr.length === 0) {
    return -1;
  } else {
    //console.log("count", count);
    if (count === target) {
      return count;
    } else {
      return -1;
    }
  }
  binarySearch(testArr);
};

 

 

이후 레퍼런스 코드를 보고 코드를 분석했다.

다음과 같이 더 간단하게 이진탐색 코드를 분석하면 되는 문제였다.

1. 왼쪽과 오른쪽에서 각각 끝 위치에서 찾을 변수를 설정하고 >> left, right
2. left가 right보다 작을 때 무한 순회
3. middle 값을 right + left를 더한 뒤 2로 나누기 
4. 그리고 arr[middle]과 target이 같은 값일 때 middle값 리턴

 

const binarySearch = function (arr, target) {
  let left = 0,
    right = arr.length - 1;
  //배열 전체에서 중간으로 잘라서 나눈 값
  //left는 0, right는 인덱스 -1, 즉 마지막 배열크기에서 -1한 값
  //left가 right보다 작을 때 무한 순회
  while (left <= right) {
    //middle은 right+left /2
    //중간 인덱스
    let middle = parseInt((right + left) / 2);
    //arr[middle]이 target과 같아지면 arr의 인덱스에서 middle이 타겟과 같아지므로 middle을 반환
    if (arr[middle] === target) {
      return middle;
    }
    //target이 arr[middle]보다 작으면 right에서 -1
    //즉 오른쪽에서 왼쪽으로 right 값이 변하면서 인덱스 이동
    if (target < arr[middle]) {
      right = middle - 1;
    }
    //즉 왼쪽에서 오른쪽으로 left 값이 변하면서 인덱스 이동
    else {
      left = middle + 1;
    }
  }
  return -1;
};