[알고리즘] 이분 탐색

이분 탐색이란?

반으로 나누어 가면서 목표하는 값을 찾아나가는 방법이다. 절반씩 나누기 때문에 시간복잡도가 O(logn)이다. 하지만 이 방법은 배열이 오름차순으로 정렬됐을 때만 사용가능하다. 만약 오름차순으로 정렬됐고, 탐색을 해야한다면 이분 탐색이 유용하다.

종류

Default

오름 차순으로 정렬된 배열에서 목표 값과 일치하는 값을 찾음

구현 과정

• left와 right를 설정(배열의 처음과 끝의 인덱스 번호)
• left가 right 보다 같거나 작다면 계속 반복
  • 중간 인덱스를 찾음
  • 목표 값과 비교해서 일치하면 끝
  • 목표 값보다 크다면 left를 mid+1로 설정하고 다시 반복
  • 목표 값보다 작다면 right를 mid-1로 설정하고 다시 반복

코드

arr = [1,2,5,7,9]
target = 7
left, right = 0, len(arr)-1
answer = -1 # 못 찾았을 경우 -1 
while(left <= right) {
  mid = (left + right) // 2
  if arr[mid] == target: 
  	answer = mid
  	break # mid 위치가 답 
  elif arr[mid] > taget: right = mid - 1
  else: left = mid + 1
}

print(answer)

upper bound

이분 탐색을 이용한 방법으로 키 값보다 큰 값이 최초로 나오는 지점의 인덱스를 찾고자 할 때 사용한다.

구현 과정

전체적인 과정은 이분 탐색과 유사하다.

• 중간 값과 키 값을 비교한다. (답이 될 수 있는 경우와 없는 경우로 나눈다고 생각하면 이해하기 쉬움)
• 중간 값이 키 값보다 작거나 같다면 이 중간 지점까진 답이 될 수 없다. 따라서 left를 mid+1로 하고 다시 범위를 좁혀나간다.
• 중간 값이 키 값보다 크다면 이 위치가 답이 될 수 있는 위치 중 최대이다. 따라서 right를 mid로 설정하고 더 작은 위치가 있는지 찾아본다.
  • 재귀는 먼저 left와 right가 같은지 체크하고 같다면 리턴을 한다. 그래서 mid로 설정해도 된다.
  • 반복문의 경우에는 left와 right가 같은 지점까지 탐색을 해야한다. 하지만 재귀와 같이 mid를 유지하면 left가 right를 초월할 수 없는 경우가 생겨 무한 루프에 빠질 수 있다. 따라서, answer에 mid를 저장하고 mid는 바꿔줘야 한다.

코드

arr = [1,2,5,7,9]
# 반복문 
target = 7
left, right = 0, len(arr)-1
answer = -1
while(left <= right) {
  mid = (left + right) // 2
  if arr[mid] <= target: left = mid+1 
  else: 
  	answer = mid	
  	right = mid - 1 # mid가 답이 될 수도 있으므로 
}
answer = left

# 재귀 
def upper_bound(s, e, p):
        if s >= e:
            return s
        mid = (s + e) // 2
        if p < arr[mid]:
          	return upper_bound(s, mid, p)
        else:
            return upper_bound(mid + 1, e, p)

lower bound

이분 탐색을 이용한 방법으로 키 값보다 크거나 같은 값이 나오는 최초의 인덱스를 찾고자 할 때 사용한다.

구현 과정

• 중간 값과 키 값을 비교한다.
• 중간 값이 키 값보다 크거나 같다면 이 중간 지점 이후로는 살펴볼 필요가 없다. 따라서 right를 mid로 하고 다시 범위를 좁혀나간다.
• 중간 값이 키 값보다 작다면 이 중간 지점까진 답이 될 수 없다. 따라서 left를 mid+1로 설정하고 다시 범위를 좁혀나간다.

코드

• 반복문

arr = [1,2,5,7,9]
target = 7
left, right = 0, len(arr)-1
while(left < right) { 
  mid = (left + right) // 2
  if arr[mid] >= target: right = mid # mid가 닶이 될 수도 있으므로  
  else: left = mid + 1
}
answer = left

arr = [1,2,5,7,9]
target = 7
left, right = 0, len(arr)-1
answer = -1
while(left <= right) { 
  mid = (left + right) // 2
  if arr[mid] >= target: 
  	answer = mid
  	right = mid - 1 # mid가 닶이 될 수도 있으므로  
  else: left = mid + 1
}
answer = left

• 재귀

# 재귀 
def lower_bound(s, e, p):
        if s >= e: # 재귀는 s, e가 같은지 먼저 확인하므로 무한 mid로 해도 무한루프에 빠지지 않는다.
            return s
        mid = (s + e) // 2
        if p <= arr[mid]:
            return lower_bound(s, mid, p)
        else:
            return lower_bound(mid+1, e, p)

=> lower_bound와 upper_bound가 같을 경우, 키 값과 같은 값이 없다는 것이다. Lower_bound는 키 값보다 크거나 같은 지점의 최초 위치를 찾는 것인데 같은 값이 없으면 큰 값을 가리키기 때문이다.