Ternary Search

[frle]

Alright guys I have a question about ternary search... So the problem is simple, you have an array of integers, actually it looks exactly like this:

int T[13] = {2, 5, 13, 45, 46, 78, 80, 95, 99, 158, 151, 116, 14};

and you have to find the index of the maximum value. The array is fully compatible with ternary search because it first strictly ascends, reaches it's maximum (which we have to find the index of) and then strictly ascends. No values repeat in the array.

Now this is the pseudocode I tried to simulate on that array (I didn't code this yet because I'm stuck simulating this on paper...):

int l = 0, u = n - 1; // lower and upper

while( l < u ) { 
  int a = l + ( u - l ) / 3;
  int b = l + 2 * ( u - l ) / 3;

  if ( T[a] > T[b] ) 
    u = b - 1;
  else
    l = a + 1;
}

Okay now following that code on paper gets me to the point where I end up with two adjacent indexes (I think 8 and 9) and then in the next iteration of while loop it would calculate a and b, but they are the same (they get a value of 8). So the loop would finish here, but... It didn't manage to find the result. It still has to eliminate 99 on index 8... What am I doing wrong?

Thank you very much in advance! :)

[frle]

Okay I solved the problem myself, but is there anything more elegant than this? Just asking, I'd like to know :P

#include <stdio.h>

int n;
int P[1000];

int ternary_search();

int main(){
    int i;
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d", &P[i]);
    printf("%d\n", ternary_search());
    return 0;
}

int ternary_search(){
    int lo = 0, hi = n - 1;
    int x1, x2;
    while (lo < hi){
        x1 = lo + (hi - lo) / 3;
        x2 = lo + 2 * (hi - lo) / 3;
        if (hi - lo == 1){
            if (P[lo] > P[hi]) return lo;
            else return hi;
        }
        if (P[x1] > P[x2]) hi = x2 - 1;
        else if (P[x1] < P[x2]) lo = x1 + 1;
    }
    return lo;
}