재귀 적으로 배열 검색

당신이 가지고있는 문제는 불충분 한 제약 검사를하고 있기 때문입니다. 확인해야하는 제약은 다음과 같습니다.

• 그것은 start배열의 길이보다 작습니다 a.
• 그것은 end배열의 길이보다 작습니다 a.
• 즉 end보다 크다 start.

그럼에도 불구하고 다음 줄 때문에 재귀가 문제가됩니다.

linearSearch(a,x,++start,end-1);

이 함수로 재귀 할 때마다 end값이 감소합니다. 즉,의 원래 입력 end이 실제로 마지막으로 확인 된 인덱스가 아닙니다.

재귀를 할 때 기본 케이스 에 대해 생각하는 것이 가장 좋습니다 . 이 경우 배열이 비어 있으면 어떻게됩니까? `false :

boolean linearSearch(int[] a, int x, int start, int end){
  if (a.length == 0) { return false; }
  // Do other things
}

우리는 또한 우리가 그 end지점을 지나고 있는지 확인해야합니다 . 이것은 기본 케이스와 동일합니다.

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  // Do other things
}

이제 head배열 (첫 번째 요소)의 start위치 가 위치 인지 결정하는 문제입니다 . 그렇지 않은 경우 동등성 검사를 건너 뛰고 수행 할 수 있습니다.

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  if (start <= 0) { //We are within the correct part of the array
     //check for equality
  } // else recurse without checking
}

평등을 확인하는 것은 다음과 if (head == x)같습니다.

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  if (start <= 0) { //We are within the correct part of the array
     if (a[0] == x) { return true; }
  } 
  //recurse
}

이제 기본 케이스 와 동등 케이스를 확인 했으므로 적절한 변수로 재귀하면됩니다. 여기서 우리는 감소 할 수 start및 end우리는 제거를 통해 하나 배열의 전체 길이를 줄일 수 있기 때문에 head. 이 모든 요소와의 또한 인덱스의 인덱스 감소 start와 end. 이렇게하면 기본 케이스가 올바르게 유지됩니다.

boolean linearSearch(int[] a, int x, int start, int end){
  if ((a.length == 0) || (end == 0)) { return false; }
  if (start <= 0) { //We are within the correct part of the array
     int head = a[0]; //The head is the first part of an array
     if (head == x) { return true; }
  } 
  // The tail is everything but the head
  int[] tail = Arrays.copyOfRange(a, 1, a.length); //Be careful of off-by-one errors!
  return linearSearch(tail, x, start - 1, end - 1);
}

제약 조건을 검토해 보겠습니다.

• 그것은 start배열의 길이보다 작습니다 a.
  • 이 start배열의 길이보다 큰 경우 먼저 false배열에 일부 요소가 있는지 확인하기 때문에이 반환됩니다. 배열이 비어 있지만에 더 높은 값이있는 지점까지 반복 된 경우 start에도 여전히 반환됩니다.
  • 경우 start제로 이하로, 우리는 평등 상태를 확인합니다.
• 그것은 end배열의 길이보다 작습니다 a.
  • 같은 이유로 end는 항상 배열의 끝이나 찾은 변수보다 작습니다. (예상되는 행동이 무엇인지 명확하지 않기 때문에 여기서 약간 속이는 것입니다.)
• 즉 end보다 크다 start.
  • 경우 end보다 적은 start우리가 반환 false도 전에 start점검 할 수있는 기회를 가지고있다.

당연히 테스트하는 데 도움이되므로 a를 사용하여 클래스에 패키지하고 main몇 가지 유용한 테스트를 구성합니다.

import java.util.Arrays;

public class LinearSearch {

    public static boolean linearSearch(int[] a, int x, int start, int end){
        if ((a.length == 0) || (end == 0)) { return false; }
        if (start <= 0) { //We are within the correct part of the array
            int head = a[0]; //The head is the first part of an array
            if (head == x) { return true; }
        }
        // The tail is everything but the head
        int[] tail = Arrays.copyOfRange(a, 1, (a.length)); //Be careful of off-by-one errors!
        return linearSearch(tail, x, start - 1, end - 1);
    }

    public static final void main(String[] args){
        int[] test_arr1 = {1,2,3,4,5};
        int[] test_arr2 = {3,2,3,1,5};
        int[] test_arr3 = {};

        // Basic success test
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 1, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 2, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 3, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 4, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 5, 0, 5));

        // Test that order doesn't matter
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 1, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 2, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 3, 0, 5));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr2, 4, 0, 5));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr2, 5, 0, 5));

        // Test that a sub array works correctly
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 3, 2, 4));
        System.out.println("Expect true Found " + LinearSearch.linearSearch(test_arr1, 4, 2, 4));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 1, 2, 4));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 2, 2, 4));
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 5, 2, 4));


        // Test empty array
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr3, 3, 1, 2));

        // Test start after finish
        System.out.println("Expect false Found " + LinearSearch.linearSearch(test_arr1, 3, 2, 1));
    }
}