Binary Search (이진 탐색)

• 이진 탐색은 정렬이 된 데이터에서 어떠한 특정 값이 존재하는지 검색하는 알고리즘이다.
• 기준 값을 통해 그 값을 기준으로 데이터를 나누어 탐색한다.
• 중복된 데이터가 없을 때는 기본적인 이진 탐색을 통해 쉽게 구할 수 있으나, 중복된 데이터들이 있는 경우엔 구할 수 없다.
• 이를 위해서는 lower bound와 upper bound를 통해 탐색해야 한다.

lower bound : 데이터 내에서 특정 값보다 같거나 큰 값이 처음 나오는 위치 탐색 가능
upper bound : 데이터 내에서 특정 값보다 처음으로 큰 값이 나오는 위치 탐색 가능

• 참고 : cherishee's tistory

Lower bound

• lower bound는 같거나 큰 값이 처음 나오는 위치를 return해야 하므로, 존재하지 않는 큰 수가 있는 경우 end를 n-1로 했을 경우, 배열의 마지막 인덱스를 넘겨준다.
• 따라서 end를 n으로 하여, 존재하지 않는 수에 대해서는 아예 인덱스 범위에서 벗어난 수를 반환하도록 한다.
• 기본 이진탐색과 다른 점은 값을 찾았을 때, 바로 return 하지 않고, 처음으로 나온 값을 찾기 위해 범위를 좁혀가며 찾는다.
• 그래서 end = mid로 놓고 범위를 좁혀간다.

def lower_bound(goal):
   start = 0
   end = n
   while (start < end):
      mid = (start + end) // 2
      if goal <= arr[mid]:
         end = mid
      else:
         start = mid + 1
   return start

Upper bound

• lower bound와 거의 유사하다.
• 단, 최초로 큰 값이 나오는 곳을 찾기위해 범위를 좁혀간다.
• 주의 : 마지막 값의 인덱스를 찾는 것이 아니다.

def upper_bound(goal):
   start = 0
   end = n
   while (start < end):
      mid = (start + end) // 2
      if goal >= arr[mid]:
         start = mid 
      else:
         end = mid + 1
   return start