[Algorithm] 이분 탐색(Binary Search) 개념 및 코드(python)

 

 

순서대로 나열되어 있는 배열이 있습니다.

이 배열에서 target 값을 찾으려 하는데, 배열 요소가 100만개라 모두 비교하면 시간이 많이 걸립니다.

이때 더 빠르게 target 값을 찾을 순 없을까요?

이 필요성을 채워주는 것이 이분 탐색 알고리즘입니다.

 

 

 

📌 이분 탐색 정의

 

 

 

이분 탐색은 정렬된 배열을 1/2씩 줄여서 타겟 값을 찾아나가는 알고리즘입니다.

 

이분 탐색의 프로세스는 다음과 같습니다.

(1) 배열의 중간 값을 찾는다.

(2) target 값과 중간 값을 비교하여 (low, same, high)큰지, 작은지, 같은지를 판단한다.

(3) target이 작다면 중간 값 이전의 배열을, 크다면 중간 값 이후의 배열을 대상으로 다시 이분 탐색을 진행한다.

(4) 만약 같다면, 중간 값이 바로 target 값이며 중간 값의 위치를 반환하고 종료한다.

 

 

 

 

📌 특성 및 시간 복잡도

 

 

a. 이분 탐색은 꼭 정렬된 배열을 이용해야 합니다.

b. 이분 탐색의 시간 복잡도는 O(logn)입니다.

*16개의 요소가 있을 때, 첫 단계에 8개 요소로 줄이고 두 번째 단계에 4개 요소로 줄입니다. 매 단계마다 1/2를 하기에 log2입니다.

*여기서 log는 log2를 말하는 것입니다.

 

 

 

 

📌 코드 구현(Python)

 

def binary_search(target, array, start, end):
  # target 값이 없는 경우를 대비한다.
  if start > end:
    return None
  
  # 이분 탐색 시작.
  mid = (start+end)//2
  if array[mid] == target:
    return mid
  elif array[mid] > target:
    return binary_search(target, array, start, mid - 1)
  else:
    return binary_search(target, array, mid + 1, end)

 

 

예시

a = [1,2,3,4,5,6,7,8,9,10,11,12]
target = 3
print(f"이분 탐색 결과 : {binary_search(target, a, 0, len(a)-1)}")


이분 탐색 결과 : 2

 

 

 

 

지금까지 이분 탐색(Binary Search)에 대해 알아보았습니다.

개념과 코드를 알았다면 활용해보는 것이 인지상정이겠죠?

 

 

https://www.acmicpc.net/step/29

이분 탐색 단계

 

 

문제를 풀면서 이분 탐색에 대한 개념을 완벽히 습득하시길 바랍니다.

수고하셨습니다.