[알고리즘] 이진 탐색 (Binary Search) - 중복된 값이 있는 경우까지 살펴보기

 

 

---

 

목차 🌠

• 개요
• 이진 탐색 설명
• 이진 탐색 template
  • Array 내에 중복된 값이 없는 경우
  • Array 내에 중복된 값이 있는 경우

 

• 주요 패턴 설명은 다음에...

 

---

 

개요

 

이진 탐색은 크기가 $n$ 인 search space에서 사용되는 탐색 알고리즘으로, worst case에서의 복잡도가 $O(\log n)$ 인 알고리즘이다. 일반적으로 이진 탐색은 정렬되어 있는 탐색 공간에 대해서 적용된다. 이진 탐색이 사용되는 경우들 중 예를 들어보자면...

 

• 정렬된 배열이 주어지고 특정 값이 추가되어야 할 위치를 물어보는 경우
• 정렬되지 않은 배열에 대해서 특정 값 보다 크거나 작은 조건을 만족하는 개수를 물어보는 경우
  • 이러한 문제는 주로 주어진 배열이 조건 만족 여부에 따라 두 개의 영역 (가능, 불가능)으로 나뉘는 경우에 사용된다.
  • 무슨말이냐면, 예를 들어 주문의 강도가 array로 주어지고 constant x 주문 강도[i]가 strength (constraint 값) 보다 큰 경우의 수를 구하고 싶다고 하자. 그러면 constant x 주문 강도[i]의 경우, 해당 값이 strength보다 작다면 주문 강도[i]보다 작은 값에 대해서는 위의 조건을 역시나 만족하지 않는다. 따라서, 주문강도[i]보다 작은 값들에 대해서는 굳이 체크를 할 필요가 없다
• 배열이 주어지지 않고 특정 범위 내에서의 조건을 만족하는 최댓값 혹은 최솟값을 물어보는 경우
  • 이 경우도 결국 위의 예제와 같다. 어떤 조건이 주어지고, 해당 조건을 만족시키도록하는 최대 혹은 최소의 $x$의 값을 묻는 문제에서 주어진 조건의 만족여부가 $x$의 값의 범위와 관련이 있다면 역시 binary search를 사용할 수 있다.

 

설명이 조금 이상하긴한데, 무튼, 이진 탐색은 단순히 탐색 용도로만 사용되지 않고 최적화 문제에도 활용될 수 있다는 점을 생각해 두면 좋을 것 같다. (자세한 패턴은 뒤에서 다루어보겠습니다)

 

 

---

 

 

이진 탐색 설명

 

이제부터는 정렬된 배열  arr  가 주어졌다고 생각하겠다. 정렬된 배열   arr  와 값   x  가 주어졌다고 하자, 그러면 $O(\log n)$의 시간 복잡도와 $O(1)$의 공간 복잡도로 이진 탐색은 다음을 수행할 수 있다:

 

•   arr  내에 존재하는   x  의 index
•   x  가 추가되었을 때도 정렬이 유지될 수 있도록 하는   arr  내의 위치 (index)

 

이진 탐색의 아이디어는 다음과 같다.

 

---

 

  arr   내에 원하는 값   x  이 존재한다고 가정해 보자. 그러면   x  는   arr   내의 어딘가에 존재할 것이다. 다른 말로 표현하자면   arr[idx] = x를 만족하도록 하는   idx  가 있고, 이 값은   0 <= idx <= len(arr)-1을 만족할 거다. 그러면 본격적으로 찾아보자. 어디서부터 찾을까 고민하지 말고 일단 존재 가능한 범위 중에서 가운데를 먼저 찔러보자. 다시 말해,   arr  의 중간 값을 먼저 확인한다. 중간 값을   arr[mid]  라고 할 때,   arr[mid]  가 찾고자 하는 값   x  보다 작다면 내가 찾고자 하는 값은   mid +1 <= idx <= len(arr)-1  사이에 존재한다. 따라서 우리가 탐색하는 범위를  mid +1 <= idx <= len(arr)-1로 바꾸는 것이다. 그러면 다시 한번 해당 범위에서 중간 값을 방문해 볼 것이다. (반대로 중간 값이 찾고자 하는 값보다 컸다면 탐색 범위는 0 <= idx <= mid-1 으로 설정된다.) (혹은, 우연찮게 우리가 찾고자 했던 값과 같았다면 그대로 mid 값을 반환하면 된다.) 이 과정이 결국 반복되는 현상임을 인지하였는가?

---

 

이 아이디어를 구체화해서 알고리즘으로 옮겨보자.

 

자 먼저, 탐색의 범위를 나타내는 변수를 도입하자. 왼쪽 범위를 나타내는 변수를   left  , 오른쪽 범위를 나타내는 변수를   right  라고 하자. 그러면 다음과 같이 구현할 수 있다:

 

1.   left = 0  ,   right = len(arr) - 1  참고로, 지금 이 변수는 탐색 영역에서 등호가 포함된다는 사실을 잊지 말자 (inclusive)
2. 우리는 탐색의 범위가 유효할 때까지 탐색을 수행할거다.
   while   arr  <=   right  :
   •  확인할 가운데 값의 index 연산하기   mid = (left + right) // 2  
   •   arr[mid]  값 확인하기:
     •  if arr[mid] == x : 찾았다! return
     •  if arr[mid] > x : x 값은 이보다 작은 범위에 존재하니까 오른쪽 범위를 줄여주자  right = mid - 1  .
     •  if arr[mid] < x : x 값은 이보다 큰 범위에 존재하니까 왼쪽 범위를 증가시키자  left = mid + 1  .

 

이 알고리즘의 경우 탐색 범위를 1/2로 계속해서 줄여나가기 때문에 시간 복잡도가 $O(\log n)$임을 알 수 있다.

 

 

---

 

이진 탐색 Code Template

arrary 내에 중복된 값이 없는 경우

def binarySearch(arr, x):

    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == x:
	        # do something with this
            return
        if arr[mid] > x:
            right = mid - 1
        else:
            left = mid + 1
    
    # if x is not in arr, left is the proper insertion point
    return left

 

arrary 내에 중복된 값이 있는 경우

 

타겟 값  x  가 여러 개 있는 경우, 제일 앞에 있는   x  를 반환하여야 할까? 아니면 제일 뒤에 있는   x  를 반환하여야 할까? 어떤 문제를 풀고 있는지에 따라서 달라질 것이다. 제일 왼쪽의   x  의 위치를 반환하는 경우와 제일 오른쪽의   x  를 반환하는 경우 두 가지 버전에 대한 template은 다음과 같다.

 

 

 

 

먼저, left-most index를 반환하는 경우를 생각해 보자.

 

일단, 알고리즘을 살짝 변형할 것이다. 앞에서와 달리, 탐색 범위를 left <= idx < right 로 수정하자. (오른쪽 등호를 없앴습니다. 참고로, 앞에서는 left <= idx <= right 였다) 그리고 추가로, 앞에서는 arr[mid] == x 인 경우 바로 반환했다면, 이번에는 반환하지 않고 이 mid 값을 새로운 탐색 범위로 지정해 줄 것이다.

 

def binarySearch(arr, x):

    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] >= x:
            right = mid
        else:
            left = mid + 1
    
    return left

 

 

앞선 경우와 달리 여기서는 탐색 범위에서 오른쪽의 등호를 빼버렸다. 그리고 최종적으로 조건을 만족할 때까지 탐색 범위를 좁힌 뒤, 탐색 범위의 왼쪽 값을 최종적인 값으로 반환한다. 그렇기 때문에 중복된 값이 있는 경우 바로 반환하지 않고 같은 값이 있을 대 제일 왼쪽 값까지 탐색을 계속한다고 이해하면 된다. 앞선 버전 (중복 값이 없는 경우)과 달라진 점을 정리해 보면 다음과 같다:

 

• 앞서 설명한 것처럼 탐색 범위에서 오른쪽 등호가 들어가지 않기 때문에  right  변수의 초기화가 달라진 것을 확인할 수 있다. (앞선 버전에서는  right = len(arr) - 1  로 초기화 했었다!)
• 앞서서 범위 체크에서  while left <= right 를 유효 범위로 봤던 것과 다르게 while left < right  while 조건문에서도 등호가 빠진다. (조금 생각해보면 이해할 수 있다. left <= idx < left 는 유효한 범위가 아니다!)
•  if arr[mid] > x  인 경우와  if arr[mid] == x 를 모두 한 번에 처리해주고 있다. 한마디로, 같은 값인 경우에도 탐색을 멈추지 않고 제일 왼쪽 값을 찾기까지 탐색을 이어가겠다는 것이다.
•  if arr[mid] >= x  일 때의 right 업데이트 방식이 달라졌다. 이전에는  right = mid + 1  이었지만, 이제는  right = mid 이다. (이 역시 유효범위 오른쪽에 등호가 들어가지 않는 것을 생각해 보면 trivial 하다)

 

한 가지 의문이 들 수 있다. 찾고자 하는 값이 하나밖에 없는 경우에도 동작하는가? 답은 "그렇다"이다. [1,2,3] 인 배열에 대해 2가 target인 경우를 쉽게 생각해 보자. left = 0, right = 3이 되고, mid = 1이 된다.

 

1) while 1 < 3, mid = 1, arr[mid] = 2 == 2 이므로 right = 1이 된다.

2) while 1 < 1이 되어버려서 탐색이 더 이상 불가능하고 while문을 종료한다

3) return 1 <-- 정답입니다 !

 

 

 

 

이제, right-most index를 반환하는 경우를 생각해보자.

 

앞의 경우와 크게 달라지는 것은 없다. 대신, 이전에는 타겟 값과 같은 경우에 right 의 범위를 왼쪽으로 좁혀줬다면, 이제 타겟 값과 같은 경우 left의 범위를 오른쪽으로 끝까지 좁혀줄 거다. 그러면 최종적으로 left <= idx < right의 범위에서 만족하는 가장 타이트한 left를 찾게 되고, left를 반환하는 경우 가장 오른쪽의 값을 반환하게 된다. 이를 코드로 나타내면 다음과 같다.

 

def binarySearch(arr, x):

    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > x:
            right = mid
        else:
            left = mid + 1
    
    return left

 

---

주요 패턴 설명은 다음에...

 

앞에서 예제로 잠깐 언급된 것처럼 이진 탐색은 단순히 탐색에만 사용되는 것이 아니라, 최적화 문제를 푸는데도 사용된다. 크게 나누어 이야기해 보자면 이진 탐색을 사용하는 대표적인 패턴에는 배열에서 활용하는 방법이 있고, 다른 하나는 특정 조건을 만족하는  min/max 값을 찾는 문제들 중 solution space를 탐색하는 데 사용될 수 있다.

두 개의 대표적인 패턴에 대해서는 다음에 다루도록 하겠다. (새로 글 작성하는 대로 본 포스팅에 백링크 걸어둘게요)

 

끝 ◼︎