trinary search에 대한 재귀 메서드 사용

Question

이진 검색 알고리즘을 수행하는 대신 배열을 3 개로 분할하고 3 진 검색 알고리즘을 사용하는 재귀 적 메서드를 작성했습니다. 재귀 사례가 옳다는 것이 상당히 긍정적이지만, 기본 사례에 문제가있는 것 같습니다. 배열에 두 개 이하의 값이 들어있는 경우에 만들어진 기본 경우는 값이 배열에 있고 인덱스를 반환하면 비 재귀 적으로 검사해야합니다. 값을 찾지 못하면 -1을 반환합니다.

내가 알 수없는 이유로,이 방법은 무엇을 상관없이 -1을 반환합니다. 배열의 크기에 관계없이 또는 배열에 값이 포함되는지 여부. 여기 방법이 있습니다.

public static int trinarySearch(int[] array, int x, int low, int high) { 

    if (high - low < 3) { //BASE CASE. 
     for (int i = low; i < high; i++) { 
      if (array[i] == x) { 
       return i; 
      } 
     } 
     return -1; 
    } else { //RECURSIVE CASE. 

     int firstThird = low + (high - low)/3; 
     int secondThird = low + 2 * (high - low)/3; 

     if (x <= array[firstThird]) { 
      return trinarySearch(array, x, low, firstThird - 1); 
     } else if (x <= array[secondThird]) { 
      return trinarySearch(array, x, firstThird + 1, secondThird - 1); 
     } else { // must be (x > array[secondThird]) 
      return trinarySearch(array, x, secondThird + 1, high); 
     } 
    } 
} 

내 테스트 코드에서 나는 단순히 [] INT 배열 = {1, 2, .....}

이의 내가 INT 2를 검색한다고 가정 해 봅시다, 그리고 같은 배열을 설정하고 배열에 있습니다. 테스트 코드에 배열을 설정하고 메서드를 trinarySearch (array, 2, 0, array.length-1)로 호출합니다. 매번 -1을 인쇄합니다. 메소드에 문제가 있습니까? 아니면 단순히 테스트 코드를 잘못 설정 했습니까?

Answer 1

로직을 low 및 high에 대해 혼합하는 것 같습니다. 일반적으로 검사 할 하위 배열을 low (포함)부터 시작하여 high (끝)까지 끝내도록 정의합니다.

사용 high 포함 (나는 array.length-1를 사용하여 예를 들어 통화에서 이해),하지만 루프

for (int i = low; i < high; i++) { 

같은 array[high]을 방문하지 않는다.

<을 <=으로 변경하면 코드가 정상적으로 실행됩니다. 그러나, 나는 그것은 또한 코드의 다른 부분 단순화하기 때문에 표준 정의 (높은 전용)를 사용하는 것이 좋습니다 :

이

• 당신은 오류가 발생하기 쉬운 +1 또는 -1 인덱스 수정의 필요하지 않습니다을 (잊지 마세요 재귀 적으로 <=에서 <으로 변경하십시오.
• high-low 검사에서 배열의 크기입니다, 그래서 당신은 더 명확하게 기본 케이스의 길이가 3

Answer 2

난 당신이 Heuster의 대답을 이해하지 않았다고 생각까지 배열을 처리하는 것을 알 수 high-low <= 3를 사용할 수 있습니다. 여기에 내가했던 것이 무엇이며 Heuster이 같은 말 것을 나에게 보인다 : 당신은 그냥 당신의 코드를 약간 변경이 if(x==splitingIndex)

입니다 재귀 섹션에서 하나 개의 중요한 조건을 놓친

public static int trinarySearch(int[] array, int x, int low, int high) { 

     if (high - low < 3) { //BASE CASE. 
      for (int i = low; i < high; i++) { 
       if (array[i] == x) { 
        return i; 
       } 
      } 
      return -1; 
     } else { //RECURSIVE CASE. 
      int firstThird = low + (high - low)/3; 
      int secondThird = low + 2 * (high - low)/3; 

      if (x < array[firstThird]) { 
       return trinarySearch(array, x, low, firstThird); 
      } else if (x < array[secondThird]) { 
       return trinarySearch(array, x, firstThird, secondThird); 
      } else { // must be (x > array[secondThird]) 
       return trinarySearch(array, x, secondThird, high); 
      } 
     } 
    } 

Answer 3

을 그 변경 사항

public static int trinarySearch(int[] array, int x, int low, int high) { 

    if (high - low < 3) { 
     //BASE CASE. 
     for (int i = low; i < high; i++) { 
      if (array[i] == x) { 
       return i; 
      } 
     } 
     return -1; 
    } else { //RECURSIVE CASE. 

     int firstThird = low + (high - low)/3; 
     int secondThird = low + 2 * (high - low)/3; 

     if(x == array[firstThird]) 
     { 
      return firstThird; 
     } 
     else if (x < array[firstThird]) { 
      return trinarySearch(array, x, low, firstThird - 1); 
     } 

     if(x == array[secondThird]) 
     { 
      return secondThird; 
     } 
     else if (x < array[secondThird]) { 
      return trinarySearch(array, x, firstThird + 1, secondThird - 1); 
     } 



      return trinarySearch(array, x, secondThird + 1, high); 
     } 
    }