Algo doubt

Question

An array a  of unknown size is filled with special symbol let's say # . Time required to find the size of a is:

Please give proper explanation

Comments

Yes it should be O(log n)

Can be implemented by modified binary search.

---

I gave Θ(1) because I thought how you would find this In actual program.

For algorithm purpose yes it is O(log n). apply binary search repeatedly and reach the rightmost element or leftmost element counting number of times binary search was applied. At last  2^count is the number of elements.

---

Please explain in a easy way how it is logn

Answer 1

First travel the array exponentially, then once you find anything other than '#', start traversing the array in reverse order exponentially( let's say you are now at loc 'n' then next loc will be n-2 then next n-4, n-8,n-16....) until you again find this symbol '#'. Now again traverse in reverse order(let's say you are at loc. m then next loc will be m+2,m+4...)until you find anything other than '#'. repeat this until you reach a point when there is a difference of 2 in between the loc. of '#' and garbage. Then do a linear access to reach the end element of the array. This whole process would take time $O(log \ n)$

Comments

Can you make your answer more clear?I am not able to understand the exponential thing

---

traverse the array elements in exponential order. Like access the first element, 2nd element, 4th element, 8th element, 16 th element and so on... This is exponential traversing.

---

Thanks sir