Java 바이너리 검색에서 반복을 구현하는 방법

1. 반복의 개념

명령어 세트나 특정 단계의 반복 실행을 반복이라고 합니다. 평신도의 용어로 하나씩 호출하십시오.

과거를 세는 기능을 구현하는 것을 반복자(iterator)라고 합니다.

2. 반복의 세 가지 요소

1. 변수 결정

반복 알고리즘으로 해결할 수 있는 문제에는 이전 값에서 직접 또는 간접적으로 지속적으로 새로운 값을 파생하는 변수가 하나 이상 있습니다. 이 변수는 반복 변수입니다.

2. 관계 설정

소위 반복 관계는 이전 값에서 변수의 다음 값을 도출하는 방법에 대한 공식(또는 관계)을 나타냅니다. 반복 관계의 설정은 일반적으로 재귀 또는 역추론을 사용하여 수행할 수 있는 반복 문제를 해결하는 열쇠입니다.

3. 프로세스 제어

반복 프로세스는 언제 종료되어야 합니까? 이는 반복 프로그램을 작성할 때 고려해야 할 문제입니다. 반복적인 과정은 끝없이 반복될 수 없습니다. 반복 프로세스의 제어는 일반적으로 두 가지 상황으로 나눌 수 있습니다. 하나는 필요한 반복 횟수가 특정 값이고 계산할 수 있는 경우이고, 다른 하나는 필요한 반복 횟수를 결정할 수 없다는 것입니다. 전자의 경우 반복 프로세스를 제어하기 위해 고정된 수의 루프를 구성할 수 있으며, 후자의 경우 반복 프로세스를 종료하기 위한 조건을 추가로 분석해야 합니다.

3. 이진 검색의 반복 예

/*非递归的折半查找*/
public static int binarySearch(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while(left <= right) {
int mid = (left+ right) / 2;
if(x > a[mid]) {
left = mid+1;
} else if(x < a[mid]) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}

루프 내의 모든 작업은 각 반복에 대해 O(1)의 비용이 들므로 분석에서는 루프 수를 결정해야 합니다. 루프는 right-left=leng-1에서 시작하고 right-left<= -1에서 끝납니다. 각 사이클 후 오른쪽-왼쪽 값은 사이클 전 값의 절반 이상이므로 최대 사이클 수는 [log(n-1)]+2입니다. 따라서 실행 시간은 O(log N)이고 재귀 시간 복잡도에는 O(N)이 필요합니다.

위 내용은 Java 바이너리 검색에서 반복을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!