[Algorithm] 이진탐색(binary search)

이진탐색(binary search)

• 리스트에서 특정 수를 찾는데 쓰이는 알고리즘
• 단순히 n개의 리스트에서 x를 찾기 위해서는 간단하게 O(n)의 시간복잡도로 풀 수 있는 방법이 있음(리스트를 전체 탐색해보면 됨). 그러나, 이 방법은 n = 1억이 되는 순간 너무나도 커지기 때문에 좀더 효율적인 알고리즘을 찾게됨
• 이진탐색은 똑같은 탐색 알고리즘이지만 O(log N)의 시간복잡도를 가짐. logN과 N은 매우 큰 차이임. 간단한 예로 n=200일 때를 생각해보면, 200번을 시행하는 것과 200, 100, 50, 25, 12, 6, 3, 1 대략 8번을 시행하는 것은 매우 큰 차이임.
• 이진탐색의 시간복잡도 : 이진탐색의 시간복잡도는 logN이라고 했는데, 어떻게 그렇게 나왔을까를 간단히 살펴보면, 일단 log N은 풀어서 써보면 '2를 몇번 곱해야 N이될까?' 이다. log2N이기 때문에 logN자체가 2를 몇번을 곱해야 N이될까를 의미하게 된다. 이러한 발상으로 보면, 아니, 사실 역으로 생각해보면, 우리는 이진탐색을 하면서 계속해서 배열을 둘로 쪼갠다(중간 인덱스를 기준으로). 그렇게 계속해서 '2' 등분을 하다가 끝에 요소가 하나 남거나 하나도 안남는 케이스까지(최악의 케이스) 탐색하게 되는데, 이걸 역으로 올라가면서 생각해보면 2를 몇번 곱해야 n이되는가 라는 말에 맞아떨어진다. 혹은 반대로 n을 몇번 2로 나눠야 1이될까를 생각해봐도 좋을 것 같다.
• 그렇다면 이진탐색은 어떻게 이러한 시간복잡도로 탐색을 할 수 있을까?. 이진탐색의 로직에 대해서 알기전에 먼저, 이진탐색이 전제로 하는 것을 알고 넘어가야하는데, 그것은 이진탐색이 가능하려면 '이미 정렬된 리스트 ' 여야 한다는 것이다.
• ?? 이미 정렬된 리스트??.. 그러면 결국 합병 정렬 등 최고로 효율적인 정렬 알고리즘을 써도 합치면 O(n log N)이 아닌가??... : 라고 생각할 수 있지만.. 사실 맞는 말이긴하다. 그러면 이진탐색은 일종의 눈속임에 불과한 것일까?. 이진탐색은 단지 사용 용도가 다를 뿐이라고 생각하면 된다. 이미 정렬된 리스트에서 특정 값을 찾는 경우에 최고로 효율적인 알고리즘이 되고, 정렬이 되어있지 않은 경우에도 만약에 특정 리스트에서 특정 값을 100,000번 찾아야할 때를 생각해보면 결국 리스트를 정렬하고 이진탐색을 하는 것이 훨씬 효율적임을 알 수 있게된다. 예를 들어, 1000개의 요소로 된 리스트에서 계속해서 다른 값을 100,000번 탐색해야할 때 일반적인 탐색 알고리즘으로는 1000 * 100,000 = 100,000,000 (1억) 번을 시행해야한다. 그러나, 한번 정렬을 하고 1000 * log21000(=10) = 10,000을 시행하며, 이진탐색으로 log21000 (=10) 의 시간복잡도로 100,000번을 탐색해야하므로 10 * 100,000 = 1,000,000(백만번)이 된다. 결론적으로 이진탐색으로 하면 초반에 정렬하는데 10,000번 + 1,000,000번 으로 총 1,010,000(백일만)번을 시행하게 된다. 앞서 말한 1억번 vs 백일만의 차이는 무시할 수 없는 차이임을 알 수 있다.
• 다시 돌아와서, 이제 본격적으로 이진탐색의 로직을 알아보면, 이진탐색은 정렬된 리스트를 가지고, 흔히 우리가 아는 '소주 병뚜껑 게임(업다운 게임)' 의 룰과 같은 방식으로 진행된다.
• 업다운 게임??.. 이진탐색의 로직을 알아보자
  1. [1, 3, 5, 6, 7, 8, 12, 15] 에서 3을 찾는 이진탐색을 예시로 설명해보려한다.
  2. 먼저, 가장 중간값을 외친.. 아니 중간 인덱스를 추출한다. 위 경우에는 (맨 처음 인덱스인 0 + 맨 끝 인덱스인 7)//2 = 7//2 = 3으로 정해진다.
  3. 다음으로, 위에서 결정된 인덱스(중간) 3에 해당하는 요소와 우리가 찾고자하는 요소를 비교한다. 위의 리스트의 인덱스 3에는 6이 있다. 고로 6과 3을 비교하면 6 > 3, 즉, 찾고자하는 값이 중간 인덱스 값보다 작음을 알아냈다.
  4. 그러면 우리는 정렬된 리스트라는 것을 알기에 이미 3을 찾기 위해 6과 6이후로 리스트의 모든 요소를 고려대상에서 제외해도 됨을 알고 있다.
  5. 그래서 이제는 남은 리스트 0부터 인덱스 3-1(6보다 작을 것이기에)인 2까지만 고려해보면 된다.
  6. 그럼 또다시 리스트의 인덱스 0-2 에 대해서 1-4의 과정을 반복한다.
  7. [1,3,5] 에서 중간 인덱스는 (0+2)//2 = 1 이고, 이에 해당하는 값은 3이다. 그래서 찾고자하는 값과 중간 인덱스의 요소를 비교해보니까 찾았다! 3=3이 됐고, 우리는 이 중간 인덱스의 값인 1이 찾고자하는 값의 위치임을 알 수 있게 됐다.
• 그렇다면 위와 같은 로직을 바탕으로 JS와 파이썬 코드로 실제로 이진 탐색을 구현해보면 다음과 같다.
  
  이진탐색 구현 코드

  ---

  with Javascript with Python