asked on

Determinig Array index when given arrayan Element without using loops; array elements follow a set pattern where next element is twice the current element

Suppose the length of array is dynamic and the elements follow the same pattern where by the next element is half the previous element. For example

1024, 512, 256, 128...

Open in new window

I would like to directly determine the index of an element. For example if I have

Open in new window

I would output index

Open in new window

without looping through the elements and comparing them with 512 then output 1. i.e not like this:

for (int i = 0;  i < length;  ++i) {
    if (array[i] == 512) { 
        printf("%d\n", i);
        break;
    }
}

Open in new window

I have been thinking of using modulus or bit manipulation like shifts but I can't get it to work. How can this be achieved?

Florian Lenschow

If your pattern really always consists of base2 exponentials (2,4,8 ...) you could use the logarithm

 log(number)/log(2)

Open in new window

In C the log is natural so you need to convert it to base 2. Then you substract the log result from the current array length, since you store them in descending order. This however depends on the value your array ends on and you might need to adjust to get the correct index. But may I ask why you need this array? Couldn't a function of n that returns the power 2^n achieve what you want to do?

ASKER CERTIFIED SOLUTION

sarabande

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Henry Korir

ASKER

The solution works well and I have a shortcut:
index=logb2((array[0])/size);
where logb2() is a function to find log to base 2, array[0] is the first element in the array and it is the largest value in the array (the array is arranged in descending order), and size is the value which it's index in the array is being determined.