[이진 탐색 | JavaScript] 기본 이해 및 시간복잡도 O(log n)

**이진탐색에 관한 설명만 필요하다면 가장 아래를 확인해주세요.

예시

여러 이름들이 나열된 배열이 있다. 이 중에서 특정 이름이 어디에 있는지 바로 알 수 있을까?

10개가 나열되어 있으면 처음부터 쭈욱 살펴보면 눈으로 금방 확인할 수 있을 것이다.

하지만 100개만 되더라도 특정 이름을 바로 확인하기엔 어렵다. 

 

예를 들어서 전화번호부에서 원하는 이름을 찾고 싶은데, ㄱ부터 찾기 시작하는데

황씨인 사람을 찾으려면 처음부터 맨 끝까지 일일히 확인해야 한다. 

하지만 우리는 황씨가 ㅎ으로 시작하므로 맨 마지막 쯔음에 있을 것을 짐작할 수 있다. 

 

이처럼 힌트가 있다면 갈피를 잡는데 수월할 수 있지만, 힌트가 없다면 우리는 유추해야 한다. 

100개의 이름을 찾는데 1부터 100을 찾아보는 것보다 좋은 방법이 있다. 

중간부터 시작하는 것이다. 황씨를 찾으려고 1부터 100을 찾기 전에,

51부터 100까지 찾아보는 방법이 경우의 수가 절반으로 줄어들게 된다. 

황씨처럼 마지막에 있음을 특정할 수 없기에 반으로 나누어보고,

중간보다 작은지 큰지 비교하자는 것이다. 

 

코드

function binary_search(arr,item){
let low = 0
let high = arr.length-1

while(low<= high){
  let mid = Math.floor((low + high)/2)
  let guess = arr[mid]
  if(guess < item){
    low = mid + 1
  }if( guess === item){
    return mid
  }if ( guess > item){
    high = mid - 1
  }else {
    low = mid+1
  }
}
}
console.log(binary_search([1,3,5,7,9],7)) //3

코드 설명

1,3,5,7,9가 담긴 배열 arr에서 7이 어디에 있는지 살펴보자.

물론 우리는 0번부터 시작해서 3번 인덱스에 있음을 쉽게 알 수 있지만 컴퓨터는 모른다.

몇번 반복될지 모르기 때문에 while반복문을 사용하였다.

또한 중간부터 살피며 점차 간격을 좁히기 때문에, low가 high와 같아질 때까지 반복하게 된다. 

 

1. 서두에 설명한 것처럼, 먼저 절반으로 나누어보는 것이다.

홀수일 경우 2로 나누면 몇번째가 중간인지 살필 때 0.5로 나뉘기 때문에, 나누고 내림해준다.

변수 guess에 배열 arr에서 mid의 인덱스를 찾아보자.

mid는 배열 arr의 low인 0값과 high값을 더하고 2를 나누어 내림한다.

즉, 0+4를 해서 2로 나누기 때문에 중간 인덱스는 2번 인덱스다. 

직접 확인해도, [1,3,5,7,9]라는 배열의 인덱스는 0,1,2,3,4 이고, 중간 인덱스는 2이다. 

guess가 답일지 아닐지는 모르지만, 일단 중간이 맞으면 바로 정답이기 때문에 

guess에 배열 arr의 mid인덱스를 넣어준다. 

 

2. 이제 guess을 확인해보자. 7을 찾아야 하는데, 2번 인덱스 guess의 값 5는 7보다 작다. 

중간값을 확인했는데 우리가 찾아야 하는 수는 중간값보다 크다는 것이다.

그렇다면, 처음에 구한 중간 값은 맨 앞과 맨 뒤를 더해서 중간을 구했는데, 더 커져야 하기 때문에,

low를 0보다 더 큰 수로 갱신해야 한다. 

 

3. 우리는 계속해서 중간을 구해가며 큰지 작은지 찾아볼 것이다. 

low가 0이 아니라 이번에는 중간값이였던 2에 1을 더해서 low가 3이 되면, 중간값이 바뀐다.

mid는 맨처음 + 맨끝인 low+high를 구하고 2로 나눌 것인데,

이번에는 0부터가 아니라 3부터 맨끝인 4를 더해서 7에서 2로 나누고 내림하여 3이 된다. 

처음에 인덱스인 2번 인덱스를 보았는데 7보다 작은 수였고, 이번엔 3번을 보게 되는 것이다.

3번 인덱스에는 7이 있다. 그리고 우리가 구한 guess값이 7이기 때문에 

해당 중간값 mid를 반환하고 마무리된다. 

구한 guess값이 구해야하는 item보다 클 경우에는 low를 크게 만드는 것이 아니라,

반대로 가장 큰 high를 줄여가며 중간값을 갱신해서 답을 구하는 것이다. 

예시 대입

숫자로 예를 들어 보겠다. 1~100 중에 70을 찾으려고 할 때, 먼저 중간인 (1+100)/2를 하고

내림하여 첫 중간값은 50으로 잡는다. 중간값 50은 70보다 작기 때문에 (50+100)/2를 한다. 

두 번째 중간값은 75다. 이제 어떤 방식인지 감이 올 것이다. 

 

즉, 처음에 1~100에서 값을 찾을 때 중간 값인 50을 찾았고, 50보다 크기 때문에 

1~50은 볼 필요가 없이 갱신된 1을 더한 low값인 51에서 100을 찾아보는 것이다. 

중간값인 75는 구해야하는 70보다 큰 숫자이다. 그렇기 때문에 이번엔 가장 큰 값을 바꿔야 한다.

50~100까지 살폈는데 75보다 작은 숫자이기 때문에 75부터는 볼 필요가 없다.

그래서 가장 높은 값은 low = 75에서 1을 뺀 74로 두고, 다시 계산한다. 

51~74를 계산하자는 것이다. 동일하게 51+74를 해서 2로 나누고.... 반복한다. 

 

이진 탐색

1~100을 하나씩 확인하면 100번 확인해야 하지만, 절반으로 줄이게 되면

경우의 수는 틀리더라도 확인해야 하는 경우가 절반으로 계속 줄게 된다. 

물론 1~100을 확인하는 방법으로 하려는데, 값이 1이라면 1번만 확인하게 되어 효율적이겠지만,

반대로 1 ~ 10000을 찾아보려는데, 최악의 경우 만번을 확인해야 한다.

그러나 이진탐색으로 찾게 되면 최악의 경우 약 13번을 확인하면 된다.

 

왜 13번이라고 바로 특정할 수 있을까? log2^10000라고 표현할 수 있는데, 

이진탐색은 시간복잡도  O(log n)이기 때문이다. n은 탐색 대상의 요소 수를 의미한다.

무슨 뜻이냐면, 우리는 10000개를 찾아볼 필요가 없이 계속 절반씩 줄이기 때문에

경우의 수가 절반씩 줄어든다는 것인데, log는 거듭제곱의 반댓말이라고 생각하면 된다.

2의 제곱은 4, 2의 3제곱은 2*2*2이므로 8이다. 쭉 2를 거듭제곱하다보면, 2^13은 8192이다.

최악의 경우 13~14번을 절반씩 줄여가며 확인해야 할 수도 있다.

 

최선의 경우 1번 확인하는 방법인 선형탐색이 더 편할 수도 있다. 선형탐색은 O(n)으로 표기한다.

하지만 최악의 경우 14번을 확인하는 것과 10000번을 확인하는 것은 너무나도 차이가 크다.

그렇기 때문에 더 효율적인 방법을 필요로 하게 되는 것이다. 

 

 

 

시간복잡도 표현이 잘 이해되지 않았는데, 이번에 정리하면서 쉽게 깨닫고 있다.