이분탐색 조금 더 이해하기

high = mid와 high = mid - 1의 차이

일반적인 이진 탐색에서는 low = mid + 1 또는 high = mid - 1을 사용합니다. 이는 정확한 값을 찾는 경우에 주로 쓰이며, 조건에 따라 탐색 범위를 한 칸씩 좁히는 방식입니다. 하지만, lower bound와 upper bound는 찾고자 하는 값이 첫 번째로 등장하는 위치 또는 값을 초과하는 첫 번째 위치를 찾는 것이 목적이므로, 다음과 같은 방식으로 처리해야 합니다.

lower bound와 upper bound에서는 high = mid 또는 low = mid가 사용되는 이유:

• lower bound: 배열에서 target 이상이 처음 등장하는 위치를 찾습니다.
  • arr[mid] >= target인 경우, mid 위치가 목표 값 또는 그 이상의 값이 등장할 수 있는 위치일 수 있으므로 high = mid로 설정합니다. 즉, 현재 범위에서 이 이상을 찾으러 더 좁혀 나가는 것이죠.
  • 만약 arr[mid] < target인 경우, 이는 우리가 찾는 값보다 작으므로, low = mid + 1로 설정해서 왼쪽은 배제하고 오른쪽만 탐색하게 됩니다.
• upper bound: 배열에서 target을 초과하는 첫 번째 위치를 찾습니다.
  • arr[mid] > target인 경우, mid 위치는 우리가 찾는 값보다 큰 값이 있는 첫 번째 위치일 수 있으므로 high = mid로 설정합니다.
  • 반면, arr[mid] <= target인 경우, low = mid + 1로 설정하여 현재 위치에서 계속 오른쪽을 탐색하게 됩니다.

이런 방식으로 high = mid로 설정하면, 범위가 점차 축소되면서 우리가 찾는 "최초로 등장하는 위치" 또는 "초과하는 첫 번째 위치"를 정확하게 찾아낼 수 있습니다.

>=와 >의 구분

• **lower bound**는 **>=**를 사용해서 찾는 값이 처음 등장하는 위치를 구합니다. 즉, 배열에서 찾는 값과 같거나 큰 값이 처음 등장하는 위치를 찾아내는 것이 목적입니다.
• **upper bound**는 **>**를 사용해서 찾는 값보다 큰 값이 처음 등장하는 위치를 구합니다.

두 값의 차이는 같은 값이 배열에서 몇 번 나왔는지를 계산하는 데 사용됩니다. 즉, upper bound - lower bound는 배열에서 해당 값이 몇 번 등장했는지를 계산하게 됩니다. 이 방식은 정렬된 배열에서 중복된 값의 개수를 세는 데 유용합니다.

예시로 이해해보자

만약 배열 arr = [1, 2, 2, 2, 3, 4]에서 target = 2일 때:

• lower bound는 2 이상이 처음 나오는 위치이므로 arr[1]이 됩니다.
• upper bound는 2보다 큰 값이 처음 나오는 위치이므로 arr[4]이 됩니다.

이 경우, upper bound - lower bound = 4 - 1 = 3이 되며, 배열에서 값 2가 3번 등장한 것을 알 수 있습니다.

따라서, upper - lower를 통해 배열에서 특정 값의 등장 횟수를 정확히 셀 수 있는 것이죠.

요약

• **high = mid**는 lower/upper bound에서 사용되어, 값을 초과하거나 최소 값을 찾기 위해 범위를 좁히는 방식입니다.
• **>=와 >**를 구분하는 이유는 lower bound와 upper bound를 정확히 계산하기 위해서이며, 이 차이를 통해 특정 값의 등장 횟수를 구할 수 있습니다.