<사업부>
이진 검색은 효율적인 — 복잡도 추정치는 O(log2(n))인 반면, 기존 순차 검색은 O(n)입니다. 즉, 예를 들어 1024개 요소의 배열에 대해 선형 검색은 최악의 경우 원하는 요소가 배열에 없을 때 모든 1024개 요소를 처리합니다. 이진 검색은 \(log_2(1024) = 10\) 요소를 처리하기에 충분합니다. 이 결과는 루프의 첫 번째 단계 이후 검색 영역이 512개 요소로 좁혀지고 두 번째 – 최대 256 등
이 알고리즘의 단점은 데이터 순서 지정에 대한 요구 사항과 일정한(데이터 양과 무관한) 시간에 모든 데이터 요소에 액세스할 수 있는 기능입니다. 따라서 이 알고리즘은 순서가 지정되지 않은 배열 및 연결된 목록을 기반으로 하는 모든 데이터 구조에서 작동할 수 없습니다.
구현
안녕 (오른쪽 – 왼쪽 > 1) // 오른쪽 테두리가 왼쪽의 오른쪽에 있는 한
NC
가운데 = (왼쪽 + 오른쪽) /< /span> 2; // 검색 영역의 중간
if (A[middle] >= b) 그렇다면
오른쪽 = 가운데; // 오른쪽 테두리 이동
그렇지 않으면
왼쪽 = 가운데; // 그렇지 않으면 왼쪽 테두리를 이동
참조
if (A[right] == X) then
오른쪽 출력;
그렇지 않으면
출력 -1;
위치:
A - 소스 배열,
N - 배열 크기,
X - 원하는 숫자.