정렬된 목록에서 이진 검색이란 무엇입니까?

순서 있는 목록의 절반 검색: 중간 값을 비교 대상으로 사용합니다. 주어진 값이 중간 값의 키와 같을 경우, 주어진 값이 중간 레코드의 키보다 작으면 검색이 성공합니다. 그러면 중간 기록의 왼쪽에서 검색이 성공합니다. 절반 영역에서 검색을 계속합니다.

이 문서의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

반검색의 개념:

반검색, 이진검색이라고도 합니다.

선형 테이블의 레코드는 키 순서(소형에서 대형 또는 대형에서 소형)로 정렬되어야 하며 선형 테이블은 순차적으로 저장되어야 한다는 전제가 있습니다.

절반 검색의 기본 아이디어는 다음과 같습니다. 순서가 지정된 목록에서 중간 값을 비교 대상으로 사용합니다. 주어진 값이 중간 값의 키와 같으면 검색이 성공합니다. 값이 중간 레코드 단어의 키보다 작으면 중간 레코드의 왼쪽 절반에서 계속 검색합니다. 주어진 값이 중간 값의 키워드보다 크면 중간 레코드의 오른쪽 절반에서 검색을 계속합니다. 검색이 성공할 때까지, 또는 모든 영역에 기록이 없어 검색이 실패할 때까지 위의 과정을 반복합니다.

알고리즘 구현:

public int Binary_Search(int[] a, int n, int key) {
int low = 1, high = n, mid;
while(low <= high) {
mid = (int)((low + high) / 2);
if(key < a[mid]) {
high = mid - 1;
}
else if(key > a[mid]) {
low = mid + 1;
}
else return mid;
}
return 0;
}

일반적으로 낮음, 높음, 중간 세 개의 포인터를 사용합니다. 검색 영역의 가장 왼쪽 값 첨자, 검색 영역의 가장 오른쪽 값 첨자, 현재 비교 값 첨자를 각각 나타냅니다.

시간 복잡성 분석:

절반 검색은 실제로 정적 순서 조회 테이블을 두 개의 하위 트리로 나누는 것과 동일합니다. 즉, 검색 중에 데이터의 절반만 찾으면 되며 이는 작업 부하의 절반에 해당합니다. 효율성을 향상시키기 위해.

관련 영상 추천: 초보부터 마스터까지 PHP 프로그래밍

위 내용은 정렬된 목록에서 이진 검색이란 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!