이진 검색 소개 및 자세한 예제

이진 검색 소개

이진 검색은 절반 검색이라고도 합니다. 이진 검색의 기본 아이디어는 사전의 요소가 작은 것부터 큰 것까지 순서대로 배열에 저장되어 있다고 가정합니다. give 고정값 키를 사전의 중간 위치에 있는 요소의 키와 비교하여 동일하면 검색에 성공한 것입니다.

그렇지 않으면 키가 작으면 전반부에서 이진 검색이 계속됩니다.

키가 크면 사전의 후반부에서 이진 검색을 계속합니다.

이렇게 하면 한 번의 비교 후에 검색 간격이 절반으로 줄어들고 검색이 성공하거나 실패할 때까지 계속됩니다.

짝수에서 중간 2개 요소 중 하나를 중간 요소로 가져옵니다.

이진 검색은 시퀀스 테이블의 키를 기준으로 사전을 정렬해야 하는 보다 효율적인 검색 방법입니다.

코드 예:

#!/usr/bin/env python
import sys 
def BinarySearch(haystack, needle):
  low = 0 
  high = len(haystack) - 1 
  while(low <= high):
    mid = (low + high)/2
    midval = haystack[mid]
    if midval < needle:
      low = mid + 1 
    elif midval > needle:
      high = mid - 1 
    else:
      print mid 
      return mid 
  print -1
  return -1
if __name__ == "__main__":
  haystack = [int(i) for i in list(sys.argv[1])]
  needle = int(sys.argv[2])
  BinarySearch(haystack ,needle)

Run:

python@pythontab:~$ python BinarySearch.py 123456789 4
3

Remarks:

1.'__': Python의 클래스 멤버는 모두 공개적이고 대중이 액세스할 수 있으므로 정통 객체 지향 언어와 같은 비공개 속성이 부족합니다.

그래서 저는 __을 사용하여 이를 처리하고 사유 재산을 시뮬레이션했습니다. 이러한 __ 속성은 내부적으로 자주 사용되며 일반적으로 재정의할 필요가 없습니다. 읽을 필요도 없습니다.

두 개의 밑줄을 추가하는 목적은 동일한 이름을 가진 일반적인 공개 속성과 충돌하지 않고, 두 번째로 개체 사용자(비개발자)가 마음대로 사용하는 것을 방지하기 위한 것입니다.

2.__name__ == "__main__"은 프로그램 스크립트가 직접 실행된다는 의미입니다.

같지 않으면 다른 프로그램에서 스크립트를 가져온 다음 해당 __name__ 속성이 모듈 이름으로 설정된다는 의미입니다.

위 내용은 이진 검색 소개 및 자세한 예제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!