[알고리즘] 이진 탐색 - JavaScript

0. 들어가며 

프로그래머스 순위 탐색 문제를 풀다가 이진 탐색을 실제로 사용해야 하는 상황이 발생해서 

정리를 해보았다. 

 

이진 탐색 자체에 대한 내용은 깊게 다루지 않고 어느 정도 이해한 상태라고 가정하고 작성한다. 

 

1. 사용 방식

[10, 30, 50, 60, 100, 200] 이란 배열이 있을 때, 기준 값으로 70이 주어지면 배열에서 70 이상의

값의 개수가 몇 개인지 확인할 때 사용하였다. 

 

2. 코드 구현

for (const item of query) {
    // item은 query의 값
    const key = item.split("and ").join("").split(" ");

    const score = parseInt(key.pop());
    const joinKey = key.join(" ");

    const value = map[joinKey];

    if (value) {
      let start = 0;
      let end = value.length;

      while (start < end) {
        const check = parseInt((start + end) / 2);

        if (value[check] < score) {
          start = check + 1;
        } else {
          end = check;
        }
      }

      answer.push(value.length - start);
    } else {
      answer.push(0);
    }
}

프로그래머스 문제를 풀 때 사용한 코드 그대로 가지고 왔다. 

 

let start = 0;
let end = value.length;
while (start < end) {
  const check = parseInt((start + end) / 2);
  if (value[check] < score) {
    start = check + 1;
  } else {
    end = check;
  }
}

핵심은 이 부분으로 

• start : 시작 워치
• end : 마지막 위치
• check : 중간 위치
• score : 기준 값
• value : 배열

시작 위치와 마지막 위치를 선언하고 반복해서 중간값과 기준값을 비교하는 방식이다. 

 

중간 값이 기준보다 작은 경우 시작 위치를 중간 위치 + 1로 변경한다. 

+ 1을 한 이유는 중간 위치까지의 값은 이미 기준보다 작기 때문에 포함시키지 않기 위해서 + 1을 했다. 

 

그리고 중간 값이 더 클 경우에는 마지막 위치를 중간 위치로 변경한다. 

이번에 - 1을 하지 않은 이유는 어차피 / 2를 하면 마지막 위치는 포함되지 않기 때문에 굳이 하지 않았다.