자료구조와 함께 배우는 알고리즘 입문 : 파이썬편 - 이진 검색 실습

이진 검색 실습

 

1. 배열, 키 사용자로부터 입력받고 키의 값에 해당하는 인덱스를 이진검색으로 찾는 함수 구현

2. 전제조건 그 배열은 오름차순이다

3. 배열 안의 값은 0보다 큰 정수이다

 

처음 구현한 코드

def binary_search(n, key):
    pl = 0
    pr = len(n) - 1
    while True:
        pc = (pl + pr) // 2
        if n[pc] < key:
            pl = pc + 1
        elif n[pc] > key:
            pr = pc - 1
        elif n[pc] == key:
            return pc
        else: return -1

n=[]
key=0

while True:                                     #리스트 입력받기
    n.append(int(input("n리스트의 인덱스를 오름차순으로 입력하시오(그만입력하려면 -1): ")))
    if  n[-1]==-1:
        n.pop
        break
    print(*n)

key = int(input("key를 입력하시오: "))
print(key)

print(f'\nkey의 값이 들어있는 n의 인덱스는 {binary_search(n, key)}이다')

 

 

최종 코드 

def binary_search(n, key):        #리스트와 키를 입력받고 리스트안에 키의 값에 해당하는 인덱스 출력하는 함수
    pl = 0
    pr = len(n) - 1
    while True:
        pc = (pl + pr) // 2

        if n[pc] < key:
            pl = pc + 1
        elif n[pc] > key:
            pr = pc - 1
        elif n[pc] == key:
            return pc         #검색성공

        if pl > pr:
            return -1         #검색실패


n=[]
key=0

n.append(int(input("n리스트의 인덱스를 오름차순으로 입력하시오(그만입력하려면 -1): ")))
while True:                                     #리스트 입력받기
    n.append(int(input("n리스트의 인덱스를 오름차순으로 입력하시오(그만입력하려면 -1): ")))
    if n[-1]==-1:     #그만입력받기
        n.pop
        break
    if n[-2] < n[-1]: #오름차순 위배
        n.pop
    if n < 0          #음수
        n.pop
    print(*n)

key = int(input("key를 입력하시오: "))            #키입력받기
print(key)

result = binary_search(n, key)
search_failure = '검색실패'

print(f'\nkey의 값이 들어있는 n의 인덱스는 {result if result != -1 else search_failure}이다')

 

처음 구현한 코드에서 미흡했던 점

1. 배열에 없는 값을 key로 넣었을 때 무한루프 발생

검색실패조건을 pl > pr로 수정

 

2. 배열을 입력받을 때 오름차순, 음수 구현 X

n[-2] < n[-1] 조건으로 구현