Problem: Turning number is the maximum number in an array which increases and then decreases. This kind of array is also named unimodal array. Please write a function which gets the index of the turning number in such an array.
Key idea: Binary Search
Key idea: Binary Search
int TurningNumberIndex(int* numbers, int length)
{
if(numbers == NULL || length <= 2)
return -1;
int left = 0;
int right = length - 1;
while(right > left + 1)
{
int middle = (left + right) / 2;
if(middle == 0 || middle == length - 1)
return -1;
if(numbers[middle] > numbers[middle - 1] &&
numbers[middle] > numbers[middle + 1])
return middle;
else if(numbers[middle] > numbers[middle - 1] &&
numbers[middle] < numbers[middle + 1])
left = middle;
else
right = middle;
}
return -1;
}
Read full article from Coding Interview Questions: No. 22 - Turning Number in an Array