피크 찾기 알고리즘 오류

Question

안녕하세요 모두는 누군가가 내 코드와 함께 나를 도울 수

당신이

갈 여기

찾는 피크가 배열을 지정해 무엇인지 궁금해하는 경우는, 피크 찾기위한 코드입니다

정수의. 그것의 피크 요소를 찾으십시오. 배열 요소는 인접 요소보다 작지 않으면 peak입니다. 모서리 요소의 경우 하나의 이웃만 고려해야합니다. 예를 들어 입력 배열 {5, 10, 20, 15}의 경우 20이 유일한 피크 요소입니다. 입력 배열 {10, 20, 15, 2, 23, 90, 67}에는 두 개의 피크 요소 인 20과 90이 있습니다. 하나의 피크 요소를 반환해야합니다.

내 문제가 배열 또는에서 첫 번째 위치에 경우 내 코드는 피크 요소를 찾을 수 나던 것입니다 마지막으로 여기에

는 그

public static void main(String[] args) { 



    int [] arr = {1,2,3,4,1,3,3,7,8,2,16}; 
    peakFinding(arr, 0,arr.length); 

} 


public static void peakFinding(int [] arr,int start ,int end){ 
    int mid = (start+end)/2; 



    if(arr[mid]<=arr[mid+1]){ 
      start = mid; 
      end = arr.length; 

      peakFinding(arr, start, end); 
     }else if(arr[mid]<=arr[mid-1]){ 

      start = 0; 
      end = mid-1; 
      peakFinding(arr, start, end); 
     }else{ 
      System.out.println("I have found peak "+arr[mid]); 
     } 

} 

Answer 1

을 감안할 때 매우 간단 내 코드입니다 당신은 단지 하나의 요소를 찾을 필요가 있으며 선택은 임의적입니다. 가장자리를 특별한 경우로 간주하십시오. peakFinding에 대한 호출 양식

if (arr == null || arr.length < 2){ 
    /*do nothing, no elements*/ 
} else if (arr[0] >= arr[1]){ 
    /*first element is peak*/ 
} else if (arr[arr.length - 1] >= arr[arr.length - 2]){ 
    /*last element is peak*/ 
} else { 
    /*call peakFinding*/ 
} 

의 코드를 포함하기 전에 나의 첫번째 검사는 또한 당신이 가진 잠재적 인 버그를 해결합니다.

이렇게하면 프로그램의 복잡한 부분이 선명하게 유지됩니다.

마지막으로, 출력 메시지는 한 곳에서 부호화한다 창 소자 (return mid;)의 위치로 복귀 peakFinding의 유형을 변경 고려한다.

Answer 2

귀하의 질문에 대답하기 전에, 내가 대신 시작과 끝이 너무 크고에 Integer.MAX_VALUE에 가까운 경우 문제가 될 수

int mid = (start+end)/2; 

의, 아주 좋아 보이지 않는 peakFinding의 시작 부분 같은 느낌 당신이 입력의 유효성을 검사하는 몇 가지 코드를 추가합니다 (배열의 널 체크를하거나 그런 < = 최종 뭔가를 시작)하는 경우, 그것은 더 나은 것

int mid = start + (end - start)/2; 

또한 시도하십시오.

이제 알고리즘에 대해 이야기하겠습니다. 이진 검색입니다.

public static void peakFinding(int [] arr,int start ,int end){ 

while(start + 1 < end) { 
    int mid = start + (end - start)/2; 
    if(arr[mid] <= arr[mid+1]) { 
     start = mid; 
    } else if (arr[mid] <= arr[mid-1]) { 
     end = mid; 
    } else { 
     System.out.println(arr[mid]); 
     return; 
    } 
} 

if(arr[start] > arr[end]) { 
    System.out.println(arr[start]); 
} else { 
    System.out.println(arr[end]); 
} 

}

Answer 3

여러분의 프로그램은 모든 피크를 찾을 수 없습니다.

예 : 첫 번째 if 절의 조건 arr[mid] <= arr[mid + 1]이 true을 반환하면 이는 배열의 오른쪽 부분에서만 피크가 검색됨을 의미합니다. 배열의 왼쪽 부분에도 피크가있을 수 있지만 배열의 왼쪽 부분은 더 이상 검색되지 않습니다.