help to know a data structure

Question

I have an assignment to write an algorithm to find duplicate in a Dynamic Sorted Array. I want to write this algoirthm but before starting, I must know the data structure Dynamic Sorted Array but, I dont know it. I tried to googling but I couldn't find anything like Dynamic Sorted Array. would you please guide me? What is this data structure and how dos it look like? thanks.

Answer 1

Let's see, you need to understand what a Dynamic Sorted array is:

You already know what a sorted array is, so let's try to understand what a dynamic array is: It's a grow able array where there is no restriction on the size of the array.

So, to summarize, you need to write an array which is:
A. Sorted
B. Dynamic in nature (expanding)

How to implement? Read Dynamic arrays overview and implementation in Java and C++

Answer 2

I think your instructor is simply referring to an array that can change and sort itself, so you can assume that it's always in the correct order and that it is of variable length. If the algorithm is to be written in pseudo-code that's probably all you need to know.

Answer 3

I would say you may have a typo in your assignment. It might ought to read "sorted Dynamic Array".

However, a dynamic array which always inserts new items in sorted order would probably fit that terminology. So take your dynamic array:

[2][5][7][9]

Inserting the element '8' would result in the following array:

[2][5][7][8][9]

Answer 4

I never heard of that data structure, but based on the individual words I would guess that it:

• Behaves like an array, that is with O(1) access operations get(index) and set(index).
• Can be resized if necessary.
• Is always sorted.

I don't think though that such a data structure is very efficient for finding duplicates. I would prefer some sort of map, unless you need very simple algorithms.

Answer 5

I assume it means an array whose length is dynamic (i.e. unknown at compile-time), and whose values are sorted.