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 :

- Look at the \(k=0\) bit of \(x\), it's either 1 or 0.
- If it's 1, binary search for the lower bound that has the \(k\)-th bit as 1.
- If it's 0, binary search for the upper bound that has the \(k\)-th bit as 0.
- 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++.

×

Problem Loading...

Note Loading...

Set Loading...