We have inherited a data structure for storing non-negative integers in an array

Q: We have inherited a data structure for storing non-negative integers in an array

For O(log N) we have to consider a fact that array must be pre-sorted and then we can use binary search technique. for ex mid=n/2; if(element==array[mid]) return else(element < array[mid]) then search in left subarray else search in right subarray.

ID: 668175 • Letter: W

Question

We have inherited a data structure for storing non-negative integers in an array.

The array has been pre-allocated and is of size M.

However, we don’t always actually use all M slots – the number of elements stored is some N < M.

The original author of the code decided to not explicitly keep track of N, but instead used a

“sentinel” approach: all values being stored are in indices [0..N-1] and after that the array is

filled with negative 1 (-1 indicating “nothing here”). (Note that N is strictly less than M).

This way if we are searching for something, we know when to stop.

Your job: devise an algorithm which takes such an array and determines N in O(log N) time.

Write your algorithm as a C function. Assume that M is a given constant.

Argue the correctness of your algorithm and why it achieves the specified runtime.

Explanation / Answer

For O(log N) we have to consider a fact that array must be pre-sorted and then we can use binary search technique.

for ex

mid=n/2;

if(element==array[mid])

return

else(element < array[mid])

then search in left subarray

else search in right subarray.

Navigate

We have implemented a circular queue(capacity: (n – 1)) using an array of size n

We have inserted the symbol E* (for Excel) to the left of each problem or part w

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

We have inherited a data structure for storing non-negative integers in an array

Question

Explanation / Answer

Related Questions

Navigate