Find max element in increasing-decreasing array

Question

Question: Find the largest in a list that list is stored as two sections, one in ascending order and the other in descending order. Elements are distinct.

E.g: Input [2 3 4 5 6 7 10 9 8 7]

Output: 10

My solution is below. Works on my unit-tests. Want to know if there any improvements from the coding point of view (esp if it is asked in an interview).

long getMaxIndex(long *arr, size_t size)
{
    long left = 0;
    long right = size - 1;

    if (arr == nil) return 0;

    while (left < right)
    {
        long mid = left + ((right-left)/2);

        if(mid == size -1)
            return mid;

        if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1])
        {
            return mid;
        }

        if (arr[mid] > arr[mid-1])
        {
            left = mid;
        }
        else
        {
            right = mid-1;
        }

        if (arr[mid] > arr[mid+1])
        {
            right = mid;
        }
        else
        {
            left = mid+1;
        }
    }

    return left;
}

Answer 1

Your code will segfault for array size = 2. Rest looks correct to me.

Specifically, for size = 2,

left = 0
right = 1
mid = 0

And hence, this line:

if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1])

will try to access arr[mid-1] which is arr[-1] and can segfault/return incorrect answer.

Answer 2

Dead code

Your code that moves the left and right bounds contains dead code. The midpoint can only be in one of three places: the left sequence, the right sequence, or in the exact middle. The first if statement is OK because it checks for the middle sequence:

    if (arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1])
    {
        return mid;
    }

However, the next part is confused:

    if (arr[mid] > arr[mid-1])
    {
        left = mid;
    }
    else
    {
        right = mid-1;
    }

    if (arr[mid] > arr[mid+1])
    {
        right = mid;
    }
    else
    {
        left = mid+1;
    }

Here, you check for mid being in the left sequence, and then move one of the bounds. Then you check for mid being in the right sequence, and then move one of the bounds again (the same one). If you consider the logic of what you are doing, the whole first if-else statement is being overridden by the second if-else. So you can remove the whole first if-else sequence and just do this:

    if (arr[mid] > arr[mid+1])
    {
        right = mid;
    }
    else
    {
        left = mid+1;
    }

Note that the first if-else was wrong anyways. If you tried doing left = mid, you would end up in an infinite loop sometimes. If you tried doing right = mid-1 you would end up with the wrong answer sometimes.

Reading out of array bounds

You successfully prevented one out of bounds condition by checking that you reached the right end of the array:

    if(mid == size -1)
        return mid;

But you didn't also check to see if you reached the left end of the array. If mid ever reaches 0, then you will read arr[-1] in the next if statement. So you should change your check to:

    if (mid == 0 || mid == size -1)
        return mid;