I have an assignment question that I am struggling with and need some direction to solve.
Suppose i have a strip of paper and i fold it from the center such that the left half goes behind the right half. Then i number the folded peices in sequence i get the numbers when i unfold as follows.
1 : 2

If i fold twice i get the numbers when unfolded as follows
1 : 4 : 3 : 2

if I fold thrice i get as follows
1 8 5 4 3 6 7 2

I want to generate the array of numbers when I fold it n times. so if i fold it for example 25 times i will get 2^25 numbers in similar sequence.

These are the observations i made

* the first and last numbers are always 1 and 2.
* the middle two numbers are always 4 and 3
* the number at index 1 is largest number and number at second last location is second largest number.
* It looks like a preorder traversal of binary search tree but I dont know how that helps.
* I tried to construct binary tree from the preorder and then convert it to inorder assuming that I can reverse this process to get the same series and I was wrong about it.

**EDIT** : For searching an element in this generated array I can do a sequential search which will be O(n) efficient. But I realise there has to be a much faster way to search for a number in this series. 

I cannot do binary search because this is not sorted and there are over a billion numbers when 25+ foldings are done. 

What kind of search tactics can i use to find a number and its index? 

This was one of the reasons I wanted to convert it into a binary search tree which will have log(n) search efficiency.

**EDIT 2:** I tried the table folding algorithm as suggested by one of the answers and it is not memory efficient. I cannot store over a billion numbers in my memory so there has to be a way to find a numbers index without actually creating the array of numbers.