이진 검색 - 가장 쉬운 방법 중 하나는 배열의 요소를 찾을 수

종종, 프로그래머, 초보자는 특정 번호를 찾을 수 있어야합니다 숫자의 집합이 있다는 사실에 직면. 그것은이 컬렉션은 배열이라고합니다. 그리고 항목을 찾기 위해 여러 가지 방법의 무수한있다. 그러나 그 중 가장 간단한 오른쪽에 이진 검색으로 간주 될 수있다. 이 방법은 무엇입니까? 어떻게 이진 검색을 구현하는 방법? 파스칼은 이러한 프로그램의 조직에 대한 쉬운 환경입니다, 그래서 우리는 공부하는 데 사용할 수 있습니다.

첫째, 분석,이 방법의 장점은 무엇인가, 그것은 우리가 이해할 수있다, 주제의 연구에서 점은 무엇인가. 그래서, 몇 가지를 찾을 필요가 적어도 100,000,000 요소의 크기와 배열을 보자. 물론,이 문제는 쉽게 우리가 배열에있는 모든 사람들과 필요한 요소를 비교합니다 사이클을 사용하는 간단한 선형 검색에 의해 해결 될 수있다. 문제는이 아이디어의 구현이 너무 많은 시간이 걸릴 것입니다. 여러 치료 및 본문의 세 줄에 간단한 파스칼 프로그램에서, 당신은 그것을 통지하지 않습니다,하지만 우리는 가지 좋은 기능의 많은 수의 다소 큰 프로젝트에 올 때, 프로그램은 너무 오래로드 할 준비가 될 것입니다. 특히 컴퓨터가 부진 경우. 따라서, 두 번 이상 검색 시간을 단축 이진 검색이있다.

그래서,이 방법의 작동 원리는 무엇인가? 바로 그것은 이진 검색은 어떤 배열이 아니라 숫자 만의 소트 세트에 작동하는지 말해야한다. 어레이의 각 단계에서 수행 중간 소자 (소자의 수를 의미 함). 필요한 경우 번호가보다 큰 평균, 모든 남아있는 것을, 즉 평균 세포보다 작은, 폐기 될 수 거기 보지. 반대로, 평균보다 작은 경우 - 오른쪽에 그 숫자 사이에, 당신은 검색 할 수 없습니다. 그러면 첫 번째 요소는 전체 어레이의 중앙 요소 및 마지막 마지막 의지 될 새 검색 영역을 선택한다. 새로운 분야의 평균 개수는 모든 세그먼트이며, (마지막 요소 + 전체 배열의 중앙 소자) / (2)의 ¼ 것이다. 또, 동일한 조작이 행해진 다 - 배열의 평균 개수와 비교한다. 목표 값이 평균보다 작은 경우, 우리는 오른쪽을 거부하고, 또한 지금이 중간 요소가 필요하지 않을 때까지, 다음에 수행 할 수 있습니다.

물론, 이진 검색을 작성하는 방법의 예를 살펴하는 것이 가장 좋습니다. 파스칼은 여기에 누군가를 맞게됩니다 - 버전은 중요하지 않습니다. 의 간단한 프로그램을 작성하자.

이 이름은 "매시브"에서 H 1의 어레이이다 "verh"평균 검색어 소위 "niz"라는 검색의 하부 경계를 나타내는 변수, 상한 - "sredn"; 그리고 필요한 수의 - "ISK".

그래서, 우리는 먼저 범위 검색의 상한과 하한을 지정합니다 :

niz = 1;
verh = H의 + 1;

그런 다음 "바닥이 상한보다 작을 때까지"주기를 구성 :

niz는 시작

각 단계에서, 우리는 세그먼트 2 분할 :

sredn = (+ niz verh) DIV (2); {나머지없이 분할하기 때문에, 함수 DIV를 사용}

검토마다. 매체가 필요한 경우 항목이 이미 발견 되었기 때문에,주기를 방해 :

іf sredn = ISK 후 중단;

보다 더 바람직한 배열의 중간 요소는 왼쪽을 무시하면, 즉 평균의 상부 경계 요소 지정 :

만약 매시브 [sredn] "ISK 다음 verh = sredn;

그리고 반대로하는 경우, 그것은 낮은 경계한다 :

다른 niz = sredn;
끝;

즉, 프로그램이 될 것 전부입니다.

우리가 실제로 바이너리 방법을 보는 방법을 살펴 보자. 1, 3, 5, 7, 10, 12, 18 그리고 12 번을 추구한다 :이 배열을 고려한다.

총에서는 7 개 요소가 있으므로 제 4의 매질, 값 7 것이다.

12 개 이상, 7, 1.3, 5 요소 때문에, 우리는 폐기 할 수 있습니다. 그런 다음 우리는 숫자 4를 가지고, 4/2 잔류 물 2. 그래서, 새로운 요소 (10)의 평균 될 것입니다.

12가 10보다 크기 때문에, 우리는 제 10, 12, 18 남아 버린다.

여기에 중간 요소가 이미 12, 그것은 필요한 번호입니다. 이 작업이 완료 - 12 번 발견합니다.