파이썬으로 이진 탐색 구현

구현 개요

파이썬으로 구현하는 이진 탐색은 2가지 방법이 있다. 첫 번째는 재귀 함수를 사용하는 것이고, 두 번째는 반복문을 이용하는 것이다.

 

---

구현을 위한 준비

target : 찾고자 하는 값
data : 오름차순으로 정렬된 list
start : data의 처음 값 인덱스
end : data의 마지막 값 인덱스
mid : start, end의 중간 인덱스

 

---

구현

1. 반복문을 사용한 구현

 

def binary_search(target, data):
    start = 0
    end = len(data) - 1

    while start <= end:
        mid = (start + end) // 2

        if data[mid] == target:
            return mid
        elif data[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    
    return None

 

2. 재귀 함수를 사용한 구현

 

def binary_search(target, data, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    if data[mid] == target:
        return mid
    elif data[mid] > target:
        end = mid - 1
    else:
        start = mid + 1
    
    return binary_search(target, data, start, end)

 

---

 

[출처 및 참고]

https://wayhome25.github.io/cs/2017/04/15/cs-16/

https://thingjin.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search-%ED%8C%8C%EC%9D%B4%EC%8D%AC

https://code-angie.tistory.com/3