No. 22 - Turning Number in an Array

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.

For example, the turning number in array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 10, so its index 5 is the expected output.

Analysis: As we know, the binary search algorithm is suitable to search a number in a sorted array. Since the input array for this problem is partially sorted, we may also have a try with binary search.

Let us try to get the middle number in an array. The middle number of array {1, 2, 3, 4, 5, 10, 9, 8, 7, 6} is 5 (the fourth number). It is greater than its previous number 4, and less than its next number 10, so it is in the increasing sub-array. Therefore, numbers before 5 can be discarded in the next round of search.

The remaining numbers for the next round of search are {5, 10, 9, 8, 7, 6}, and the number 9 is in the middle of them. Since 9 is less than is previous number 10 and greater than its next number 8, it is in the decreasing sub-array. Therefore, numbers after 9 can be discarded in the next round of search.

The remaining numbers for the next round of search are {5, 10, 9}, and the number 10 is in the middle. It is noticeable that number 10 is greater than its previous number 5 and greater than its next number 9, so it is the maximum number. That is to say, the number 10 is the turning number in the input array.

We can see the process above is actually a classic binary search. Therefore, we can implement the required function based on binary search algorithm, as listed below:

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;

}

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.