코드의 오류 (도움이 필요함)

Question

현재 작업하고있는 프로젝트에서 필수적이므로이 코드를 사용하려고합니다.

import java.util.Scanner; 
public class BinarySearch 
{ 
    int binarySearch(int arr[], int l, int r, int x) 
    { 
     if (r>=l) 
    { 
     int mid = l + (r - l)/2; 

     if (arr[mid] == x) 
      return mid; 

     if (arr[mid] > x) 
      return binarySearch(arr, l, mid-1, x); 

     return binarySearch(arr, mid+1, r, x); 
    } 
    return -1; 
} 

public static void main(String args[]) 
{ 
    BinarySearch ob = new BinarySearch(); 
    Scanner sc = new Scanner(System.in); 
    System.out.println("Enter number of inputs:"); 
     int i = sc.nextInt(); 
     int arr[] = new int[i]; 
    System.out.println("Enter array of inputs:"); 
     for(int j = 0;j < i; j++){ 
      arr[j] = sc.nextInt(); 
    } 
    System.out.println("What number do you want the index from"); 
     int n = arr.length; 
     int x = sc.nextInt(); 
     int result = ob.binarySearch(arr,0,n-1,x); 
     if (result == -1) 
      System.out.println("FAILURE"); 
     else 
      System.out.println("Element found at index "+result + "."); 
    } 
} 

결과가 배열이 작동 할 수있는 정상적인 입력이라고 기대합니다. 내가 얻는 실제 결과는 "아마도 무한 루프가 있습니다."라는 시간 초과 오류입니다.

Answer 1

binarySearch는 괜찮은 것 같습니다.

그러나 이진 검색은 정렬 된 배열에서만 작동합니다 (비교 결과에 따라).

실제로 시간 초과는 루프 또는 재귀가 종료되지 않는다는 것을 의미합니다. 재귀 고려

• 경우 : l < = R
• int mid = l + (r - l)/2
• 따라서 주어진 L < = 중간 & & 중간 < = R
• 다음 [l, <r] (좁은)
• 에 binarySearch(arr, l, mid-1, x); 일 후 은 [>l, r] (작음)에서 작동합니다.

재귀가 종료됩니다.

정렬되지 않은 배열에서도 (가비지 생성).

스캐너 사용법에 문제가있는 것처럼 보입니다. hasNextLine, hasNextInt, nextInt 및 nextLine으로 깨끗한 사용법을 보지 못했습니다.

클래스 Arrays은 sort을 제공 할 수 있습니다 (또한 자체적으로 binarySearch을 가짐).

---

코드

는 테스트하지 않으며, 일반적으로 나는 Scanner이 System.in를 들어, 그래서 아마 더 간결하게 쓸 수있는 사용하지 않는 :

BinarySearch ob = new BinarySearch(); 
Scanner sc = new Scanner(System.in); 

System.out.println("Enter number of inputs:"); 
if (sc.hasNextLine() && sc.hasNextInt()) { 
    int i = sc.nextInt(); 
    sc.nextLine(); 

    int arr[] = new int[i]; 
    int n = arr.length; 

    System.out.println("Enter array of inputs:"); 
    for (int j = 0; j < i; j++) { 
     if (sc.hasNextLine() && sc.hasNextInt()) { 
      arr[j] = sc.nextInt(); 
      sc.nextLine(); 
     } else { 
      ... 
      System.exit(1); 
     } 
    } 

    // Important, binary search relies on the array being sorted: 
    Arrays.sort(arr); 
    System.out.printf("The sorted array is %s%n", Arrays.toString(arr)); 

    System.out.println("What number do you want the index from?"); 
    if (sc.hasNextLine() && sc.hasNextInt()) { 
     int x = sc.nextInt(); 
     sc.nextLine(); 
     int result = ob.binarySearch(arr, 0, n-1, x);