Please resolve this bug!

[prakhs]

I have an array of elements.
Think each of the element as competitors, and a tournament is going to rank them.
The output of the program is showing elements at each level.
Here's the code:

#include <stdio.h>
#include <stdlib.h>

bool isPowerOfTwo (int x)
{
  /* First x in the below expression is for the case when x is 0 */
  return x && (!(x&(x-1)));
}
// modified
int log_2(unsigned int n) {
    int bits = 0;
    if (!isPowerOfTwo(n))
        bits++;
    if (n > 32767) {
        n >>= 16;
        bits += 16;
    }
    if (n > 127) {
        n >>= 8;
        bits += 8;
    }
    if (n > 7) {
        n >>= 4;
        bits += 4;
    }
    if (n > 1) {
        n >>= 2;
        bits += 2;
    }
    if (n > 0) {
        bits++;
    }
    return bits;
}

int second_minima(int a[],unsigned int n) {
    int log_2n = log_2(n);
    int **p = (int **) (malloc(log_2n * sizeof(int *)));
    int i, j, k;
    for (i = 0, j = n; i < log_2n; i++) {
        j = j&1 ? j/2+1 : j/2;
        p[i] = (int *)(malloc(j * sizeof(int)));
    }
    for (i = 0; i < n; i++)
        p[0][i] = a[i];
    for (i = 1, j = n; i < log_2n; i++) {
        for (k = 0; k+1 < j; k += 2) {
            if (p[i-1][k] > p[i-1][k+1]) {
                p[i][k/2] = p[i-1][k];
                //printf("%d\n", p[0][n-1]);
            }
            else {
                p[i][k/2] = p[i-1][k+1];
            }
        }
        if (j&1)
            p[i][j/2] = p[i-1][j-1];
        j = j&1 ? j/2+1 : j/2;
    }
    for (i = 0, j = n; i < log_2n; i++) {
        for (k = 0; k < j; k++)
            printf("%d ",p[i][k]);
        printf("\n");
        j = j&1 ? j/2+1 : j/2;
    }
    return 0;
}

main()
{
    int n;
    scanf("%d", &n);
    int a[n];
    int i;
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    second_minima(a,n);
    return 0;
}

The problem is with this input instance:
Input :
13
12 7 3 18 4 2 16 5 6 17 1 8 9
Output :
12 7 3 18 4 2 16 5 6 17 1 8 12
12 18 4 16 17 8 12
18 16 17 12
18 17
18
Correct Output :
12 7 3 18 4 2 16 5 6 17 1 8 9
12 18 4 16 17 8 9
18 16 17 9
18 17
18

The problem is it is turning the last element of level 0 to first element.
This is occuring at line 49. I dont know why it is changing p[0][n-1] to p[1][0].
Can any one explain the fault.
I have tested it with other inputs, its giving right answer.

[Ancient Dragon]

Have you used a debugge on that so that you can see the value of the variables on each loop iteration? My guess that behavior is happening is because k/2 is beyond the bounds of the array which causes array overflow and unpredictable results.

Terrible description of the problem.

[prakhs]

ok, I will try to explain again.
Suppose there are n integers. There will be a competition between pair of integers (1st vs 2nd, 3rd vs 4th, 5th vs 6th and so on). The integer which is greater in the pair will go to next level and it will have competition with the winner of the next pair (for eg winner of 1st and 2nd vs winner of 3rd and 4th). This winner will go on to next level and so on.
If the last integer has no one to pair with it will go on to next level without any competition.
for eg: if there are seven integers

5  8 9 5 2 3 7
 \/  \/  \/  |
 8    9   3  7
  \  /     \/
   9       7
    \     /
       9

@ Ancient Dragon, The value of the last integer of level 0 (i.e. p[0][n-1]) changes when line no. 49 executes 1st time. Instead of just updating value of first integer of level 1 (i.e. p[1][0]) to 12, it also changes p[0][n-1] to 12.

Ok, What I think the problem is: p[0][n-1] is pointing to the same location as p[1][0]. So, updating p[1][0] also changes p[0][n-1]. Can any one explain me why they are pointing to same location! ??

[prakhs]

At last solved!
What a terrible mistake.
line 41 should come after line 42!! I was not allocating the required space to pointer.
Anyways thanks for giving your time.

If that works, given the description of your problem, that is probably one of the worst /obfuscated unecessary solutions I've ever seen.

You've got logs, mallocs and bit shifting for what should be a trivial solution.

[prakhs]

Actually I was interested in the strategy for finding second maximum/minimum in n + log(n) - 2 comparison using tournament method.

In tournament method, every number (element) is paired with other number successively to find the maximum number. This forms a tree like structure. We must have n-1 comparisons to find maximum number.

The information gained while finding max number will be used in reducing the comparisons for second largest. It means, we would need to consider only those which will lost against max number to be considered for second largest.

From the tree structure, we can conclude such lost numbers can't be more than [log(n) - 1] (consider tree height).

Overall, at minimum we need ( n - log(n) - 2 ) comparisons.

That might be so however, but you're banking on your maths to be absolutely spot on. Why take that risk and just come up with a simple algo to get it right every time.

For a speed/ how efficient your program is competition yours might be better - For real life, real world apps where ease of understanding, maintainability and zero bugs it's defintely worse.