[알고리즘] 이진 탐색 알고리즘(1)

 

본 포스팅에서는 이진 탐색 알고리즘에 대한 정리 내용을 담고있습니다.

(본 알고리즘 포스팅은 유튜브 '이코테 2021 강의'를 참고하여 작성하였습니다.)

 

 

https://www.youtube.com/@dongbinna

동빈나

 

 

---

 

순차 탐색과 이진 탐색

순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

 

이진 탐색의 동작 예시)

이미 정렬된 10개의 데이터 중에서 값이 4인 원소 찾기

 

 

 

 

 시작점 : index 0, 끝점 : [9], 중간점 : [4] (소수점 이하는 제거)

우리가 찾고자 하는 원소 4보다 중간점의 원소 8이 큰 상황임.

따라서 중간점을 기준으로 오른쪽에 있는 값들은 볼 필요가 이제 없음

 

 

따라서 위와 같이 '끝점'을 기존 중간점의 왼쪽으로 위치를 옮긴다. 

끝점의 index는 3, 중간점의 index는 1이 된다. 

이번에는 우리가 찾고자하는 값인 4보다 중간점의 값인 2가 작은 상황이다.

따라서 중간점 기준으로 왼쪽의 값들은 볼 필요가 없다. 

 

 

 

그래서 이번에는 위와같이, 시작점을 기존 중간점의 오른쪽으로 위치를 옮긴다. 

이때 우리가 찾고자하는 수와 중간점의 수가 같게 되고, 찾고자했던 수 4의 위치를 알 수 있게 된다. 

 

 

위의 이진 탐색 과정을 파이썬 코드로 구현하면 다음과 같다. 

 

① 재귀 함수로 구현

def binary_search(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2      #2로 나눈 몫
  if array[mid] == target:
    return mid     #찾으면 중간점의 인덱스 반환
  elif array[mid] > target:
    return binary_search(array, target, start, mid-1)   #타겟이 중간점 값보다 작으니까 끝점을 중간점의 바로 왼쪽으로 옮김
  else:
    return binary_search(array, target, mid+1, end)

n , target = list(map(int, input().split()))  #n은 원소의 개수, target은 찾으려는 값\
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
  print('원소가 존재하지 않습니다.')
else:
  print(result + 1)   #반환하는 값이 index 이기때문에 +1 해주어야함.

 

 

② 반복문 구현

def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) //2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid-1
    else:
      start = mid + 1
  return None

n , target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
  print('원소가 존재하지 않습니다.')
else:
  print(result + 1)

 

 

 

추가로 파이썬에는 이진 탐색을 가능하게 하는 이진 탐색 라이브러리가 있다. 

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

 

from bisect import bisect_left, bisect_right

a = [1,2, 4, 4, 8]
x = 4

print(bisect_left(a,x))    # 2출력
print(bisect_right(a,x))   # 4출력

 

위의 예시와 같은 방식으로 동작한다. 

이런 이진 탐색 라이브러리를 사용하면

값이 특정 범위에 속하는 데이터의 개수를 손쉽게 구할 수 있다.

 

 

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
  right_index = bisect_right(a, right_value)
  left_index = bisect_left(a, left_value)
  return right_index - left_index

a= [1,2,3,3,3,3,4,4,8,9]

#값이 4인 데이터의 개수 출력
print(count_by_range(a, 4, 4))

#값이 [-1, 3] 범위에 있는 데이터의 개수 출력
print(count_by_range(a, -1, 3))

위와 같은 방식으로 사용이 가능하다.