[알고리즘] ✨ 이진 탐색

이진 탐색이란?

이진 탐색이란 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.

어떻게 동작하나요?

이진 탐색은 탐색 범위를 절반식 좁혀가며 데이터를 탐색하므로, 앞에서부터 차례로 탐색하는 순차탐색보다 데이터를 훨씬 빠르게 찾을 수 있다는 장점이 있다.

다음은 이진 탐색이 동작하는 방식이다.

1. 배열의 중간에 있는 임의의 값(중간값)을 선택하여 찾고자 하는 값 X와 비교한다.
2. X가 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.
3. 해당 값을 찾을 때까지 1과 동일한 방법을 반복한다.

절반식 찾아야할 범위가 좁혀지므로 시간복잡도는 O(logN)이된다.

구현방법

이진탐색은 재귀함수와 반복문으로 구현할 수 있다.

재귀함수 코드

def binary_search(array, target, start, end):
  if start > end:
    return None
  mid = (start+end)//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())
array = list(map(int, input().split())

result = binary_search(array, target, 0, n-1)
if result == None: 
  print("원소가 존재하지 않습니다.")
else:
  print(result + 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)