python 이분법 찾기 알고리즘 실현 방법[재 귀 와 비 재 귀]
이분법 찾기
2 분 검색 은 절반 검색 이 라 고도 부 르 는데 장점 은 비교 횟수 가 적 고 검색 속도 가 빠 르 며 평균 성능 이 좋다 는 것 이다.검사 대기 표 가 질서 있 는 표 이 고 삭제 가 어렵 다 는 단점 이 있다.따라서 반절 찾기 방법 은 자주 변동 하지 않 고 빈번 한 서열 표를 찾 는 데 적용 된다.먼저,표 의 요 소 는 오름차 순 으로 배열 되 고 표 중간 위치 에 기 록 된 키 워드 를 검색 키워드 와 비교 하 며 이들 이 같 으 면 성공 적 으로 찾 을 수 있다 고 가정 합 니 다.그렇지 않 으 면 중간 위치 기록 을 이용 하여 시 계 를 앞,뒤 두 개의 서브 시트 로 나 누고 중간 위치 기록 의 키워드 가 키 워드 를 찾 는 것 보다 크 면 앞의 서브 시트 를 찾 고 그렇지 않 으 면 뒤의 서브 시트 를 찾 습 니 다.이상 의 과정 을 반복 합 니 다.조건 을 만족 시 키 는 기록 을 찾 아 검색 에 성공 하거나 하위 표 가 존재 하지 않 을 때 까지 찾 을 수 없습니다.
이분법 찾기 실현
(비 귀속 실현)
def binary_search(alist, item):
first = 0
last = len(alist)-1
while first<=last:
midpoint = (first + last)/2
if alist[midpoint] == item:
return True
elif item < alist[midpoint]:
last = midpoint-1
else:
first = midpoint+1
return False
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
def binary_search(alist, item):
if len(alist) == 0:
return False
else:
midpoint = len(alist)//2
if alist[midpoint]==item:
return True
else:
if item<alist[midpoint]:
return binary_search(alist[:midpoint],item)
else:
return binary_search(alist[midpoint+1:],item)
testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))
False
True
시간 복잡 도
본 논문 에서 말 한 것 이 여러분 의 Python 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
로마 숫자를 정수로 또는 그 반대로 변환그 중 하나는 로마 숫자를 정수로 변환하는 함수를 만드는 것이었고 두 번째는 그 반대를 수행하는 함수를 만드는 것이었습니다. 문자만 포함합니다'I', 'V', 'X', 'L', 'C', 'D', 'M' ; 문자열이 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
