amchacon - 2 months ago 19

C++ Question

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:

- 1 = True
- 2 = True
- 4 = True
- 8 = True
- 16 = True
- 32 = False

Step back to 16, and search in 16-32 range:

- (16+1) = True
- (16+2) = True
- (16+4) = True
- (16+8) = False

Step back to 20 (16+4) and start over:

- (20+1) = True
- (20+2) = False

Start over in 21:

- (21+1) = False

Ok, so the size is 21.

This is my implementation in code:

`#include <iostream>`

#include <vector>

using namespace std;

int inBounds(const vector<int>& arr,int i)

{

return i < arr.size();

}

int size(const vector<int>& arr)

{

int init = 0;

while (inBounds(arr,init))

{

int start = 2;

while (inBounds(arr,init+start))

{

start *= 2;

}

start /= 2;

init += start;

}

return init;

}

int main()

{

vector<int> arr;

for (int i = 0;i < 1000;i++)

{

arr.resize(i);

int n = size(arr);

if (n != arr.size())

cout << "FAIL " << arr.size() << ' ' << n << endl;

}

return 0;

}

This works good. But i don't know the exactly cost of this algorithm. The first search is indeed log(N), but now i need to add the subrange searchs. So i have my doubts about the real cost

Answer

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.