O(logn) approach:

int max_value_in_semisorted_array(int* arr, int start, int end)

{

if (start == end) return arr[start];

int middle = (end + start) / 2;

if (arr[middle] > arr[start])

return max_value_in_semisorted_array(arr, middle, end);

else

return max_value_in_semisorted_array(arr, start, middle);

}

Simply walk the array to find the max in O(n) time. Compare the current max to the next element all the way until the end of the array.