4
\$\begingroup\$

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;
}
\$\endgroup\$
  • 8
    \$\begingroup\$ Please add a language tag, it will remove some guesswork and may influence answers (as well as raising the questions visibility). \$\endgroup\$ – forsvarir Oct 3 '16 at 6:22
  • \$\begingroup\$ Thanks for adding a language tag. Although you did add two. Is it C or Objective-C? Despite the commonalities in the names, those languages are quite different. I would guess that it is C. \$\endgroup\$ – Simon Forsberg Oct 3 '16 at 17:12
  • \$\begingroup\$ Yes, you are right this particular code is all C. Removed objective-C \$\endgroup\$ – Smart Home Oct 3 '16 at 17:13
  • 1
    \$\begingroup\$ arr == nil is not C. Maybe you should change that to arr == NULL. \$\endgroup\$ – JS1 Oct 3 '16 at 18:02
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.