So yesterday I sent a code of this search in a group chat as a joke but surprisingly everyone praised it and iframe_ dubbed it as "Fenwick search" and now I am farming contribution making a blog about it.

Fenwick Search

Lets say you want to search on the interval $$$[1, n)$$$ and lets say you want to find the minimal position that satisfy a certain property. Also let the minimal position that satisfies said property be $$$ans$$$

So, in regular binary search you keep a left bound and a right bound and you change them accordingly, but in Fenwick search you only keep track of the middle bound. Firstly initialize the middle bound as the highest power of 2 that is less than n.

The gist of Fenwick search is transforming the middle bound into $$$ans$$$, we do that by manipulating the bits in the middle bound. Specifically for every set bit in $$$ans$$$ we set the bit after the last set bit in the middle bound and we shift it left until it matches the desired bit in $$$ans$$$. For example, lets say we start with middle bound $$$16$$$ and we want to transform it into $$$ans = 22$$$, $$$16_{10} = 10000_2 \rightarrow 11000_2 \rightarrow 10100_2 \rightarrow 10110_2 = 22_{10} $$$

But how do we actually transform it? Well its simple, we check if the middle bound satisfies the property if so, you shift the last set bit one to the left, if it does not satisfy you need to set a new bit after the last set. You need to perform this checking and updating exactly $$$\lfloor{log2(n - 1)}\rfloor$$$. There is a single edge case, if the middle bound is $$$\ge n$$$ you always need to shift the last bit to the right.

To set a new bit after the last set you need to update the middle bound like this: $$$m = m + (m \ \text{&} \ (-m)) \gt \gt 1$$$ and to shift the last bit to the right you need to update the middle bound like this:$$$m = m - (m \ \text{&} \ (-m)) \gt \gt 1$$$

int tm = 1<<(LOG);
int ans = -1;
for(int i = 0;i < LOG;i++){
    if(tm >= n)tm -= (tm & -tm) >> 1;
    else if(check(tm)){
        ans = tm;
        tm -= (tm & -tm) >> 1;
    }else tm += (tm & -tm) >> 1;
}

This is the code, $$$check(x)$$$ is function that checks the property the we are searching

That's it, sorry for my bad english I tried to make it as good as possible