Leetcode - 162. Find Peak Element

문제

배열에서 peak 지점의 인덱스를 리턴하라. 만약 peak가 여러개면 아무지점이나 리턴해도 된다. 배열의 양 끝은 -∞ 라고 가정해라. (단 arr[i] != arr[i+1] 항상 성립한다)

아디이어

peak지점은 inc-dec 지점이다. 만약에 한 지점 i를 선택했는데

• 왼쪽값이 더 작다면 즉, arr[i-1] < arr[i] 라면, peak는 반드시 i이상 우측에 존재한다는 뜻.
• 오른쪽값이 더 작다면 arr[i] > arr[i+1], peak는 반드시 i이하 왼쪽에 존재한다는 뜻.
  따라서 이렇게 탐색 범위를 1/2 씩 좁히는 바이너리 서치를 할 수 있다.

해결

binary search 템플릿 사용.

Input: nums = [1,2,1,3,5,6,4]
Output: 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.

int findPeakElement(int* nums, int numsSize){
    int left = 0, right = numsSize - 1, mid = 0;
        
    while (left < right) {
        mid = left + (right - left) / 2; 
        if (nums[mid] > nums[mid+1]) {  // 답은 좌측(0 ~ mid) 중에 존재한다. 
            right = mid;
        } else { 						// 답은 우측(mid+1 ~ size-1) 에 존재
            left = mid + 1;
        }
    }
    return left;
}

이건 맨 처음 풀어봤던 조금 더 비효율적인 풀이.

int findPeakElement(int* nums, int numsSize){
    int left = 0, right = numsSize - 1, mid = 0;
    // check input valid range : 
    if (numsSize == 0) {
        fprintf(stderr, "invalid input\n");
        return 1;
    }
        
    while (left < right) {
        mid = left + (right - left) / 2; 
        if (mid - 1 >= 0 && nums[mid - 1] > nums[mid]) {
            right = mid - 1;
        } else if (mid + 1 < numsSize && nums[mid] < nums[mid + 1]) {
            left = mid + 1;  
        } else { 
            return mid;
        }   
        /* 처음에 나머지 조건을 모두 체크 했는데 이럴 필요가 없음
        } else if (((mid - 1 >=0 && mid + 1 < numsSize) && (nums[mid - 1] < nums[mid] && nums[mid > nums[mid - 1]])) ||
                     mid == 0 && nums[mid + 1] < nums[mid] || 
                     mid == numsSize - 1 && nums[mid] > nums[mid - 1]) {
            return mid;
        }
        */
    }
    return left;
}