BinarySearch 프로그램을 작성하면서 프로그램을 작성했습니다.
def binary_search(array, x, low=0, high=None):
if high is None:
high = len(array)
while low < high:
mid = (low+high)//2
midval = array[mid]
if midval < x:
low = mid+1
elif midval > x:
high = mid
else:
return mid
return -1
다음을 넣을 때 :
binary_search([1,2,2,3],2)
프로그램이 제공하는 출력은 다음과 같습니다.
2
그러나 프로그램이 찾은 첫 번째 정수 'x'의 색인을 출력으로 제공하고 싶습니다. 따라서 이전 예에서는 '2'대신 '1'이됩니다. 이것을 어떻게 바꿀 수 있는지에 대한 아이디어가 있습니까?
얼리 아웃 (최종 else조건) 을 제거 하고 이전 elif을 스트레이트로 대체해야합니다 else. 루프가 종료 될 때만 동등성을 테스트하고 발견 된 인덱스를 반환하도록 선택하거나 -1찾을 수없는 경우 :
def binary_search(array, x, low=0, high=None):
if high is None:
high = len(array)
while low < high:
mid = (low+high)//2
if array[mid] < x:
low = mid+1
else:
high = mid
return -1 if low >= len(array) or array[low] != x else low
그것은 일반적으로, 당신은 루프 당 다중 비교를 수행하지 않기 때문에 이런 식으로 행동하는 것도 좋은 생각이다 ( <그리고 >것 유형에 따라 비용이 수, 각 호출 비교,); 루프 당 정확히 하나의 숫자가 아닌 비교로 단순화하면 시간이 절약됩니다 (종종 더 빠르게 실행됩니다. Python 라이브러리는 종종 <및을 직접 구현 하고 ==래퍼를 사용하여 <및 측면에서 다른 비교기를 구현하므로 ==속도가 느려집니다).
이것은 실제로 무엇 bisect.bisect_left에서와 순수 파이썬 구현 ; 그렇지 않으면 코드와 거의 동일합니다. log(n)값의 가장 왼쪽 인스턴스를 식별하기 위해 전체 단계를 수행 할 가능성이 더 높기 때문에 시간이 더 오래 걸리지 만 입력에 반복되는 값 이 많지 않으면 일반적으로 증분 비용이 적습니다 .
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다