[알고리즘/자바스크립트] Binary Search Algorithm (이진 탐색 알고리즘)

Binary Search(이진탐색)

만약 어떤 친구가 1부터 10까지 중에 숫자 하나를 생각한 다음 우리에게 그 숫자가 뭔지 맞춰보라고 했다고 생각해보자. 이 때 그 숫자를 맞추기 위해 1부터 10까지 하나 하나 이 숫자가 맞는지 물어본다면 우리는 최악의 경우에 10번을 질문해야할 것이다.

 

그런데 만약에 우리가 1과 10의 가운데 숫자를 부르고 맞춰야 할 숫자가 그 숫자보다 작은지 큰지 친구가 알려준다면 어떻게 될까?

 

만약에 우리가 맞춰야할 숫자 x가 3이라고 해보자.

1과 10의 중간 숫자인 5와 비교한다.

 

x < 5

1

2

3

4

5

6

7

8

9

10

 

우리가 찾는 숫자는 5보다 작으니까 5보다 큰 숫자는 모두 지울 수 있다.

이제 검색할 범위가 절반 이하로 줄어들었다. 이제 1과 5의 중간인 2와 비교한다.

 

x > 2

1

2

3

4

3은 2보다 크기때문에 2보다 작은 숫자는 모두 지운다.

이제 검색할 범위가 또 절반으로 줄었다.

 

x == 3

3

4

3을 찾았다!

 

 

이진 탐색은 순차 탐색에 비해 엄청나게 빠른 속도로 원하는 데이터를 찾을 수 있다.

한 번에 엄청나게 많은 데이터를 검색 범위에서 줄일 수 있기 때문에 

1부터 100사이의 숫자 중 검색한다면 어떤 숫자를 찾던지 최대 7번 만에 정답을 찾을 수 있다.

이진탐색을 사용하면 240,000개의 데이터도 최대 18번 만에 답을 찾을 수 있다.

심지어 40억 개의 데이터를 검색한다고 해도 최대 32번 만에 답을 찾을 수 있다.

 

n개의 원소를 가진 리스트에서 단순 탐색을 사용하면 최대 n번의 탐색이 필요하다.

이 것을 Big O 표기법으로 O(n)이라고 표기하고 선형 시간이라고 부른다.

 

이진 탐색을 사용하면 최대 log n번만에 답을 찾을 수 있다.

이 것을 Big O 표기법으로 O(log n)이라고 표기하고 로그 시간이라고 부른다.

 

이진 탐색은 매우 빠른 속도로 데이터를 찾을 수 있지만

반드시 데이터가 정렬되어있어야만 한다.

 

 

function binarySearch (target, dataArray) {
  let low = 0;
  let high = dataArray.length - 1;
  let mid = Math.floor((high + low) / 2);
  while (target !== dataArray[mid]) {
    if (target < dataArray[mid]) {
      high = mid - 1;
      mid = Math.floor((high + low) / 2);
    } else {
      low = mid + 1;
      mid = Math.floor((high + low) / 2);
    }
  }
  return dataArray[mid];
}

 

숫자가 든 배열에서 이진 탐색으로 원하는 숫자를 찾아내는 함수를 구현해보았다.

이 함수의 문제점은 dataArray에 내가 찾는 target 값이 없으면 무한 루프에 빠진다는 점이다.

게다가 mid 값을 계산하는 똑같은 구문이 계속 반복되어 적혀있다.

그래서 로직을 다시 바꿨다.

 

 

function binarySearch (target, dataArray) {
  let low = 0;
  let high = dataArray.length - 1;
  
  while (low <= high) {
    let mid = Math.floor((high + low) / 2);
    let guess = dataArray[mid];

    if (guess === target) {
      return guess;
    } else if (guess > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return undefined;
}

 

수정한 코드는 이렇다. low가 high보다 작거나 같으면 계속해서 반복을하며 범위를 좁혀나간다.

만약에 범위가 딱 하나로 좁혀지는 순간 guess와 target의 값을 비교해서 같으면 그 값을 return하고 

같지 않으면 high는 mid - 1, low는 mid + 1이기 때문에 low의 값이 high보다 커질 것이다.

그러면 반복문을 종료하고 데이터가 없으므로 undefined를 리턴한다.

 

 

 

위 코드로 정말 240,000개의 데이터를 18번 만에 찾아낼 수 있는지 확인해보려고 한다.

var arr = [];
for (let i = 1; i <= 240000; i++) {
  arr.push(i);
}

function binarySearch (target, dataArray) {
  let low = 0;
  let high = dataArray.length - 1;
  
  let index = 0;
  while (low <= high) {
    let mid = Math.floor((high + low) / 2);
    let guess = dataArray[mid];

    if (guess === target) {
      return guess;
    } else if (guess > target) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
    index++;
    console.log(`${index}. low: ${low}, mid: ${mid}, high: ${high}, data: ${dataArray[mid]}`);
  }
  return undefined;
}

 

arr라는 배열에 1부터 240,000까지의 숫자를 순차적으로 넣는다.

그리고 binarySearch 함수로 arr 배열에서 원하는 숫자를 찾는 과정을 콘솔 창에 출력해보았다.

 

 

var result = binarySearch(1200, arr);
console.log(result);

 

1200을 넣고 테스트해보았다.

12번 만에 정답을 찾았다.

 

 

그렇다면 240000을 찾아보면 결과가 어떻게 나올까?

이렇게 17번 만에 정답을 찾아낸다.

만약에 단순 탐색으로 240000을 찾았다면 240000번이나 검색을 했을 것이다.

 

 

---

Log 로그

분명 학교 다닐 때 배웠지만 기억에서 까마득히 사라졌기에 로그 시간을 이해하기 위해서 다시 한 번 찾아보았다.

이 표현은 쉽게 말해서 10을 몇 번 곱해야 100이 되는지 묻는 것이다. 그러니까 답은 2가 된다. 

 

 

Big O 표기법에서 사용하는 모든 로그 시간은 2가 생략된 것이다.

 

그러니까 예를 들어서 배열에 숫자가 8개가 있다면 단순 탐색을 하면 O(n)의 시간이 걸리므로

최악의 경우 8번을 탐색해야 한다.

 

그러나 이진 탐색을 하면 O(log n)의 시간이 걸리므로 log8 = 3,

즉 최대 3번만 확인하면 숫자를 찾을 수 있다.