이진 검색을 구현하는 Java 코드 예제

이 글에서는 주로 Java 바이너리 검색 관련 정보를 소개하고 있습니다. 필요한 친구들은

알고리즘

을 참고하세요. 그룹 수는 3, 12, 24, 36, 55, 68, 75, 88입니다. 주어진 값을 확인하려면 24입니다. 변수 front, mid, end 각각 데이터의 상한, 중간, 하한을 가리킴, mid=(front+end)/2.　　

front=0(3을 가리킴), end=7(88을 가리킴) ), mid=3(36을 가리킴) ). mid>x이므로 문단의 전반부에서 검색해야 합니다.

새 end=mid-1=2, front=0을 변경하지 않고 그대로 두고 새 mid=1을 지정합니다. 이때 x>mid이므로 후반부에 검색해야 합니다.

새로운 front=mid+1=2, end=2를 변경하지 않고 그대로 두고, 새로운 mid=2, 이때 a[mid]=x, 검색에 성공합니다. 검색하려는 숫자가 순서대로의 숫자가 아닌 경우(예를 들어 x=25) 세 번째 판단이 이루어졌을 때 x>a[mid]라면 위의 규칙에 따라 front=mid+1, 즉 , front=3, front>end가 나타납니다.

의 경우 검색에 실패했다는 의미입니다.

예: N개의 요소가 있는 정렬된

배열 에서 사용자가 입력한 데이터 x를 찾습니다. 알고리즘은 다음과 같습니다.

1. 검색 범위 front=0, end=N-1을 결정하고 중간 항 mid=(front+end)/2를 계산합니다.

2. a[mid]=x 또는 front>=end이면 검색을 종료하고, 그렇지 않으면 아래쪽으로 계속 진행합니다.

3. a[mid]x이면 찾을 요소의 값이 중간 요소보다 작은 범위에만 있을 수 있음을 의미하며 mid-1의 값을 end에 할당합니다. , mid를 다시 계산하고 2단계로 이동합니다.

알고리즘 복잡도 분석

시간 복잡도

1. 최악의 상황 찾기 마지막 요소(또는 첫 번째 요소) 석사 정리 T(n)=T(n/2)+O(1) 따라서 T(n)=O(logn)

　2. 최선을 찾는 경우 중간 요소 O(1), 검색된 요소는 중간 요소(홀수 길이 배열의 가운데 요소, 짝수 길이 배열의 왼쪽 가운데 요소)

공간 복잡도:

S(n)=n

아아아아

위 내용은 이진 검색을 구현하는 Java 코드 예제의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!