바이너리 서치 python (binary search python)

바이너리 서치란?

---

• 정렬 된 자료를 반으로 나누어 계속하여 탐색하는 방법
• 정렬 할 자료는 오름차순 이어야 함
• 퍼포먼스가 좋음

구현시 필요한 변수

---

target : 찾고자 하는 목표 값
data : 오름차순으로 정렬 된 list (찾을 위치)

start : data의 처음 값 index
end : data의 마지막 값 index
mid : start - end 의 중간 값

구현 (재귀)

---

def bin_search(data, target, start, end):
    idx = (start + end) // 2
    mid = data[idx]

    if target == mid:
        print(f'idx: {idx}')
        return
    elif mid > target:
        bin_search(data, target, start, idx-1)
    elif mid < target:
        bin_search(data, target, idx+1, end)

    else:
        return




target = 25
data = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(data)

data.sort()
start = 0 
end = length-1
print(data)
bin_search(data,target,0,end)

idx = 3

Reference

---

1. https://velog.io/@madfinger/Binary-Search%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC
2. https://wayhome25.github.io/cs/2017/04/15/cs-16/