The problem is the next:
We want to know the size of an vector, we can't use size() but we have a function inBounds(vector& arr,int index) that returns true if the index is a valid position of the vector.
So, my approach is iterate positions. Starting at 1 and duplicating (2,4,8,16,32...) until that inBounds returns false, step back so and repeat the search in the subrange.
Let's do an example, put N = 21:
using namespace std;
int inBounds(const vector<int>& arr,int i)
return i < arr.size();
int size(const vector<int>& arr)
int init = 0;
int start = 2;
start *= 2;
start /= 2;
init += start;
for (int i = 0;i < 1000;i++)
int n = size(arr);
if (n != arr.size())
cout << "FAIL " << arr.size() << ' ' << n << endl;
seems like your first subrange search is also logN (since it uses basically same algorithm as the initial part) while your final subrange search is linear (iterating over every value), but it's very much bounded and a small fraction of N. i would say your algorithm is roughly c * logN, where c is a small value representing the number of subsearches you're doing, so O(logN) in general.