이분검색(반값검색)(##비교횟수는어떻게집계하나##)

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 함수에 파라미터를 설정할 필요가 없다는 것이다.

좋은 웹페이지 즐겨찾기