04. 이진탐색 - 이진탐색, 순차탐색, lower/Upper Bound

< 이진탐색의 진행 과정 > 

앞에서 배열에서 원하는 값을 찾기 위해선, 모든 값들을 하나씩 다 확인해야 하므로 O(N)이 나온다.

배열 속 값이 수백만, 수천만, 심지어 수억개라면 어떨까요?

우리는 검색을 빠른 시간내에 할 필요가 있기 때문에, 탐색을 할 수 있는 다른 방법을 찾아야 합니다.

 

업/다운 게임이라는 것을 들어보셨나요?

한 사람이 수를 생각하고, 다른 사람이 수를 예측해서 부르면 그것보다 큰지, 작은지 불러주면서 최대한 빨리 그 수를 맞추는 게임입니다. 많은 사람들이 수를 처음 예측할 땐 범위의 가운데에 해당하는 숫자를 부르고, 그 이후엔 업/다운에 맞춰 특정 구간의 가운데를 부르는 방법으로 수를 추측합니다.

이진탐색의 아이디어도 저것과 동일합니다. 찾아야 하는 수의 범위 중 가운데의 값과 찾고자 하는 값을 비교하여 대소관계에 따라 특정 구간으로 이동하는 것을 반복하는 것입니다.

업/다운 게임에서 비춰보면, '다운'이라는 말을 들으면 우리는 그 값보다 더 작은 값을 선택해야 하고, '업'을 외쳤다면 더 큰 값을 선택해야 합니다. 이진탐색에서도 저러한 과정을 수행하기 위해선, 당연하게도 대소관계에 따라 실제 찾는 값도 작거나 커져야 하기 때문에 배열에 들어있는 값은 반드시 정렬되어야 합니다.

당연히 우리가 찾는 범위 속 원소의 갯수가 1개로 줄어들 때 까지 계속 탐색을 진행해야 하기 때문에 while문을 통해 조건을 걸고, 이후 중간에 위치한 값의 대소관계에 따라 left와 right의 값을 계속 바꿔가면서 진행하는 것을 볼 수 있습니다.

 

단, while 조건을 걸 때 left <= right 이렇게 등호를 꼭 넣어야 단 하나의 숫자만 남았을 경우에도 올바르게 찾아집니다.

계속 탐색을 반복하며, 그 중 가운데 위치에 해당하는 값인 arr[mid]와 찾으려고 하는 숫자인 target이 일치하면, 해당 위치인 mid를 반환해주게 됩니다. while문이 끝났는데도 불구하고 아직 return이 되지 않았다면, -1을 반환해 원하는 값이 없다는 표시를 해주게 됩니다. 또, mid = (left + right) / 2 에서 left + right 값이 홀수라면, mid는 2로 나눈 뒤 버림한 위치에 가게됨에 유의합니다.

왜 left는 mid + 1이고, right는 mid - 1일까요? arr[mid]값이 target값이 아니었으니 mid는 target을 포함할 숫자 범위에서 명확히 제외됩니다. 따라서 mid 위치를 제외한 범위로 left, right를 움직여줘야 함에 유의합니다.

 

function solution(arr, target)
  set left = 0
  set right = arr.size - 1
  while left <= right
    set mid = (left + right) / 2
    if arr[mid] == target
      return (1)mid

    if arr[mid] > target
      (2)right = (3)mid - 1
    else
      (4)left = (5)mid + 1
      
  return -1

 

< 이진탐색과 순차탐색 >