v2 time O(log(n)) space O(log(n)) Accepted

could have tested with a simple test case to avoid the bug in v1