[알고리즘] 이진 탐색(Binary Search, 이분 탐색)

이진 탐색(Binary Search)

---

이진 탐색(Binary Search) 란?

정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X 와 비교한다. X 가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터를 대상으로, X 가 중간 값보다 크면 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다. 

 

---

코드(Python)

# 반복 알고리즘 

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] > target:
            high = mid - 1
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            low = mid + 1
    return -1

 

# 재귀 알고리즘
def binary_search(array=list(), target=int(), left=int(), right=int()):
    """
    이진 탐색 - 재귀 함수 구현
    :param array: 배열 
    :param target: 찾고자 하는 값 
    :param left: 왼쪽 인덱스 
    :param right: 오른쪽 인덱스 
    :return: target index
    """
    if left > right:
        return None
    mid = (left + right) // 2     # 중간값. 몫
    if target == array[mid]:
        return mid
    elif target > array[mid]:
        return binary_search(array=array, target=target, left=mid + 1, right=right)
    else:
        return binary_search(array=array, target=target, left=left, right=mid - 1)

array=[-1, 0 , 3, 5, 9, 12]     # 정렬된 리스트!

result = binary_search(array=array, target=9, left=0, right=len(array) - 1)
if result: 
    print(result)
else:
    print("없다")