[Algorithm] 이진 탐색은 뭐야?

이진 탐색(Binary Search)란 탐색 범위를 1/2로 줄여가면서 정보를 탐색하는 알고리즘 방법이다.

 

범위를 1/2씩 줄이면서 탐색을 진행하기 때문에 탐색 속도가 빠르다는 장점이 있지만 정렬되지 않은 배열에서는 사용할 수 없다는 장점이 있다.

 

이진 탐색은 "오름차순 배열에서 가운데 값이 목푯값보다 작다면 가운데 기준 왼쪽 배열은 무조건 목푯값보다 작다. "라는 결론처럼 비교를 통해서 논리적 결론을 도출하는 방식이다.

 

다음은 이진 탐색에 사용되는 배열을 시각화한 자료이다.

 

이진 탐색 1번째

위의 배열에서 목표값을 8이라고 가정하고 이진 탐색을 진행하겠다. 진한 회색은 탐색을 마친 값, 파란색은 중간값, 노란색은 목푯값, 초록색은 탐색 완료 값이라고 하겠다.

 

이진 탐색 2번째

가운데 값(5)이 목표값(8)보다 작기 때문에 가운데 값 왼쪽 배열은 탐색할 필요가 없으므로 다음으로 넘어간다.

 

이진 탐색 3번째

가운데 값(7)이 목표값(8)보다 작기 때문에 가운데 값 왼쪽 배열은 탐색할 필요가 없으므로 다음으로 넘어간다.

 

이진 탐색 4번째

가운데 값(8)이 목표값(8)과 같기 때문에 해당 위치 값 출력 후 탐색 종료한다.

 

해당 과정을 코드로 표현하면 다음과 같다.

 

def BinarySearch(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2
  if array[mid] == target:
    return mid
  # 가운데 값이 목표값보다 작은 경우(가운데 기준 왼쪽 확인)
  elif array[mid] > target:
    return BinarySearch(array, target, start, mid-1)
    # 가운데 값이 목표값보다 큰 경우(가운데 기준 오른쪽 확인)
  else:
    return BinarySearch(array, target, mid+1, end)
 
array = [0,1,2,3,4,5,6,7,8,9]
target = 8
result = BinarySearch(array, target, 0, len(array)-1)
print(result)

 

함수의 인자로 배열과 목푯값 그리고 배열의 시작과 끝점을 넣어준다.