[알고리즘] 이진 탐색 알고리즘

이진 탐색 알고리즘은 정렬된 배열에서 반으로 쪼개가며 숫자를 찾는 알고리즘이다.

 

과정을 살펴보자.

 

찾고자 하는 수를 target 라 두고 배열의 중간 인덱스 값을 mid 라고 두자.

 

1. target 은 arr[mid] 보다 큰가?

2. target 은 arr[mid] 보다 작은가?

3. target 은 arr[mid] 와 같은가?

 

1인 경우 mid 의 오른쪽 부분을, 2인 경우 mid 의 왼쪽 부분을, 3인 경우 return 하면 된다.

 

재귀를 배웠으니 재귀를 활용하여 구현해보자.

 

def BinarySearch(arr,target,left,right):
    mid = (left + right)//2
    if target<arr[mid]:
        return BinarySearch(arr,target,left,mid-1)
    elif target>arr[mid]:
        return BinarySearch(arr,target,mid+1,right)
    elif target == arr[mid]:
        return True # 값이 존재한다.
    else:
        return False  # 값이 존재하지 않는다.

 

간단하게 구현 가능하다.