Binary Search on Bits

Chris realize his computer couldn't perform accurate comparisons on integers. That is, his computer couldn't evaluate if a > b is true or false.

He has a sorted array of $n$ integers and he needs to find if the number $x$ is within the array. He doesn't want to perform a linear search, so he came up with another idea of Binary Search. Here is the algorithm :

1. Look at the $k=0$ bit of $x$ , it's either 1 or 0.
2. If it's 1, binary search for the lower bound that has the $k$ -th bit as 1.
3. If it's 0, binary search for the upper bound that has the $k$ -th bit as 0.
4. Increment $k$ by 1 and go back to step 1.

What is the time complexity of this algorithm? Or if you think this algorithm doesn't work, choose the option "This algorithm doesn't work".

Details and Assumptions

• Notice that this algorithm doesn't use any of the following operators : < > <= >= .
• This algorithm is written in Python, where there is no upper bound for $x$ like C++.