이분검색(반값검색)(##비교횟수는어떻게집계하나##)
8134 단어 블루 브리지 컵
이분 검색
n값(1<=n<=1000), n개의 비강하 순서로 배열된 정수와 찾으려는 수 x를 입력하고 이분 찾기 알고리즘으로 x를 찾고 출력 x가 있는 하표(0~n-1)와 비교 횟수를 입력한다.x가 존재하지 않으면 출력 -1과 비교 횟수를 출력합니다.입력 형식: 총 세 줄 입력: 첫 번째 줄은 n 값;두 번째 줄은 n개의 정수이다.세 번째 줄은 x값이다.출력 형식: 출력 x가 있는 하표(0~n-1) 및 비교 횟수.x가 존재하지 않으면 출력 -1과 비교 횟수를 출력합니다.입력 예제: 4 1 2 3 4 1 출력 예제: 0 2
다음 코드는 반복으로 구현됩니다.
import java.util.Scanner;
public class Main{
static int[] num;
static int count=0,index=-1;
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
num=new int[n];
for(int i=0;i<n;i++) {
num[i]=sc.nextInt();
}
int target=sc.nextInt();
recursion(0,n-1,target);
System.out.println(index);
System.out.println(count);
}
public static void recursion(int low,int high,int target) {
if(low<=high) {
count++;
int mid=(low+high)/2;
if(num[mid]>target) {
recursion(low, mid-1, target);
}
else if(num[mid]<target) {
recursion(mid+1, high, target);
}
else if(num[mid]==target)
{
index=mid;
}
}
}
}
결과 표시:
4
1 2 3 4
1
0
2
문제에 부딪혔습니다. 솔직히 2분을 이용해서 찾아보면 사상이 어렵지 않고 코드도 알아볼 수 있습니다. 통계 비교 횟수에 있어서 저는 문제에 부딪혔습니다.이 알고리즘은 전역 변수를 정의하고 수조를 전역 변수로 설정할 때 Recursion 함수에 파라미터를 설정할 필요가 없다는 것이다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Blu-Bridge 컵 -- Excel 주소문제 설명 Excel 셀의 주소는 열 번호를 알파벳으로 표시하는 흥미로운 것을 나타낸다. 예를 들면, A는 첫 번째 열을 나타냅니다. B는 두 번째 열을 나타냅니다. Z는 26열을 나타냅니다. AA는 27열을 나타냅...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.