July 30, 2021 - binary search(오름차순 정렬데이터)

*7월30일

-어제 질문 받은 binary search를 혼자서 풀어보기로 했다. 오름차순으로 정렬된 데이터가 있고, 함수에 특정한 값을 던지면 특정한 값과 가장 가까운 정렬된 데이터를 뽑는 문제였다.

-6개월 과정 동안 개인적으로든 수업에서든 한번 마주했던 것으로 기억나는데, 막상 손으로 풀어보려니 기억이 잘 안나서 배열 내 모든 데이터와 전수 비교하는 식으로 어거지로 풀이했다.

 

-어제 풀이해주신 이론대로 다시 한 번 풀어봤는데, 중첩 if문이 너무 많은 것 같아 이 방법이 맞는지 잘 모르겠다. 시간을 두고 좀 더 개선해봐야겠다.

 

 

  //이진탐색, 오름차순으로 정렬된 데이터에만 적용
  array = [1, 3, 5, 6, 7, 12, 15, 17, 30, 35, 37, 39, 45, 55, 62, 77, 79, 80];
  var low = 0;
  var high = array.length - 1;
  var mid = Math.floor((low + high) / 2);
  var closestVal;
  var gap = Math.max.apply(null, array); //배열 내 최대값
  var cnt = 0;

  getClosestVal(62);

  function getClosestVal(input) {

    while (mid < high && mid > low) {

      if (array[mid] == input) {
        cnt++;
        closestVal = array[mid];
        console.log("loop count : " + cnt);
        console.log("low : " + low);
        console.log("high : " + high);
        console.log("mid : " + mid);
        console.log("gap : " + gap);
        console.log("closestVal : " + closestVal);
        return closestVal;
      } else if (array[mid] > input) {
        high = mid;
        mid = Math.floor((low + high) / 2);
        cnt++;

        if (gap > Math.abs(array[mid] - input)) {
          gap = Math.abs(array[mid] - input);
          closestVal = array[mid];
        } else if (gap == Math.abs(array[mid] - input)) {
          closestVal = array[mid];
          console.log("loop count : " + cnt);
          console.log("low : " + low);
          console.log("high : " + high);
          console.log("mid : " + mid);
          console.log("gap : " + gap);
          console.log("closestVal : " + closestVal);
          return closestVal;
        }
      } else if (array[mid] < input) {
        low = mid;
        mid = Math.floor((low + high) / 2);
        cnt++;

        if (gap > Math.abs(array[mid] - input)) {
          gap = Math.abs(array[mid] - input);
          closestVal = array[mid];
        } else if (gap == Math.abs(array[mid] - input)) {
          closestVal = array[mid];
          console.log("loop count : " + cnt);
          console.log("low : " + low);
          console.log("high : " + high);
          console.log("mid : " + mid);
          console.log("gap : " + gap);
          console.log("closestVal : " + closestVal);
          return closestVal;
        }
      }
    }
  }