이진 탐색(search) 알고리즘 정리-파이썬

n=[1,2,3,4,7,10] #이미 정렬되어 있는 리스트에 대해 동작.

#이진 탐색
search_num = int(input('search_num:'))
f=0  #f: 리스트 검색 시작위치
l=len(n)-1  #l: 리스트 검색 마지막위치
while f<=l:#시작위치와 끝위치가 역전되지 않는한 반복
    m=(f+l)//2  #리스트 중간 위치 찾기
    if n[m]>search_num:     #중간값보다 찾는 값이 작으면 찾는 값이 중간값 앞에 있음
        l=m-1               #l를 중간 앞으로 이동
    elif n[m]<search_num:   #중간값보다 찾는 값이 크면 찾는 값이 중간값 뒤에 있음
        f=m+1               #f를 중간값 뒤로 이동
    else:                   #n[m]==search_num 인 경우로 m번째 방에서 찾음을 의미
        print('found. idx:', m) #break로 루프 빠져나옴
        break

if f>l:     #f>l은 위 루프에서 break로 종료되지 않았음을 의미하고 이는 찾는 값이 없음을 의미
    print('not found')

 

재귀적구현.

 

 

정렬리스트에서 이진탐색(빠른속도위해)으로 특정범위 수의 갯수구하기: