Python 3 바이너리 검색 정렬 된 변수 (숫자 목록)

Question

안녕하세요 :) 저는 정렬 된 목록을 통해 이진 검색을 사용하는 프로그램을 작성했습니다. 다음과 같이 작동합니다 : 그것은 1 2에있는 경우 프로그램이 숫자 3을 찾아야한다 3 1 2 3

파이썬 find.py 1 2 3

그것은 사실 및 인쇄 발견 바늘을 반환해야 3, false를 돌려 인쇄가 발견되지 않은 경우는 1 2 및 3에없는 경우는 ....

def binary_search(needle, haystack): 
first = 0 
last = len(haystack) - 1 
itemlist = str(input(haystack)) 
sorted(itemlist) 

while first <= last: 
    mid = (first + last)/2 
    if itemlist[mid] == needle : 
     print("Found the needle in the haystack") 
     return True 
    elif needle < itemlist[mid]: 
     last = mid - 1 
    else: 
     first = mid + 1 
    if not True: 
     print("Did not find the needle in the haystack") 
     return False 

그래서 표준 바이너리 서치 알고리즘을 구현했지만, 내가 건너 온 모든 버전은하지 않습니다 다음 숫자를 모두 검색해야하는 항목으로 첫 번째 숫자를 가져 오십시오. 내 질문은, 어떻게해야합니까? 첫 번째 변수를 "항목"으로 지정한 다음 항목을 포함 할 수도 있고 포함하지 않을 수도있는 목록으로 모든 것을 가져올 수 있습니까?

또한 x 길이의 목록을 정렬해야하므로 정렬 된 함수를 시도했지만 목록 길이가 될 수 있으므로 변수를 정렬해야합니까? 나는 거기에 조금 붙어있어 ....이 주제에 대한 도움말?

Answer 1

sys.argv은 파이썬 프로세스를 호출하는 데 사용되는 명령 줄 인수가 들어있는 목록입니다. sys.argv[0]은 스크립트의 이름이고 sys.arv[1:]은 나머지 인수입니다. 이 같은 접근을 : 먼저 건초 더미를 정렬해야하는 경우

def binary_search(needle, haystack): 
    print('binary_search(): needle = {}, haystack = {}'.format(needle, haystack)) 
    # your implementation here 

if __name__ == '__main__': 
    import sys 

    if len(sys.argv) > 2: 
     needle = sys.argv[1] 
     haystack = sys.argv[2:] 
     binary_search(needle, haystack) 
    else: 
     print('Usage: {} needle haystack...'.format(sys.argv[0])) 

---

사용 sorted()는 : 즉 N (O를 가지고 있기 때문에

binary_search(needle, sorted(haystack)) 

그러나, 첫 번째 분류에 약간의 포인트가 log n) 시간 복잡도, 반면에 선형 검색은 O (n) 시간 복잡성이 있습니다. 따라서 입력이 정렬되지 않은 경우 대상을 찾을 때까지 목록을 반복하여 검색하는 것이 좋습니다.

---

마지막으로 검색이 작동하려면 입력을 숫자 값으로 변환해야 할 수도 있습니다.

Answer 2

이진 검색은 표준 라이브러리의 일부입니다.이 검색은 int()을 사용할 수 있습니다. 문제를 해결하는 방법은 다음과 같습니다.

import sys 
import bisect 

argv = [int(_) for _ in sys.argv[1:]] 
x = argv.pop(0) 
i = bisect.bisect_left(argv, x) 
print("Found:", i != len(argv) and argv[i] == x) 

또한 입력 목록이 이미 정렬 된 경우에만 문제가 발생합니다. 그렇지 않은 경우 선형으로 정렬되는 x in argv을 사용하면됩니다 (목록 정렬은 선형 함수입니다).