python 중 2분 검색법의 실현 방법
1, 2분 찾기
질서정연하고 중복되지 않은 목록에서 이 목록의 요소를 찾습니다.
2. 특징
(1) 질서정연한 목록에 맞추어야 한다
(2) 이 목록은 중복되지 않아야 합니다.
(3) 아래 첨자 색인에 따라 찾기
3. 사용 방법
비귀속 실현:
def binary_search(alist, item):
""" """
n = len(alist)
start = 0
end = n - 1
while start <= end:
mid = (start + end) // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
end = mid - 1
else:
start = mid + 1
return False
if __name__ == '__main__':
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# print(binary_search(li, 55))
# print(binary_search(li, 100))
def binary_search_2(alist, item):
""" """
n = len(alist)
if 0 == n:
return False
mid = n // 2
if alist[mid] == item:
return True
elif item < alist[mid]:
return binary_search_2(alist[:mid], item)
else:
return binary_search_2(alist[mid + 1:], item)
if __name__ == '__main__':
li = [17, 20, 26, 31, 44, 54, 55, 77, 93]
# print(binary_search(li, 55))
# print(binary_search(li, 100))소개
2분 검색은 절반 검색(Binary Search)이라고도 하는데 이것은 효율이 비교적 높은 검색 방법이다.그러나 절반 찾기 요구 선형 테이블은 반드시 순서 저장 구조를 사용해야 하고 테이블의 요소는 키워드에 따라 질서정연하게 배열되어야 한다.
전제
찾을 순서가 정해져야 합니다.
시간 복잡도
O(log2n)
원리
1) 해당 기간의 중간 위치 확인 K
2) 찾은 값 t와array[k]를 비교하고 같으면 이 위치로 되돌아오는 데 성공합니다.그렇지 않으면 새로운 검색 영역을 확인하고 2분 검색을 계속합니다.
3) 영역 확인 절차:
만약array[k]>t, 수조가 질서정연하기 때문에array[k,k+1,...,high]>t;그러므로 새로운 구간은array[low,..., K-1]이다.
반대로,array[k]
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
