Binary search of a sorted array takes logarithmic search time, but the time to insert a new element is linear in the size of the array. We can improve the time for insertion by keeping several sorted arrays.
Specifically, suppose that we wish to support SEARCH and INSERT on a set of n elements. Let k = [lg (n + 1)], and let the binary representation of n be nk-1, nk-2, ..., n0. We have k sorted arrays A0, A1, ..., Ak-1, where for i = 0, 1, ..., k - 1, the length of array Ai is 2i. Each array is either full or empty, depending on whether ni = 1 or ni = 0, respectively. The total number of elements held in all k arrays is therefore. Although each individual array is sorted, there is no particular relationship between elements in different arrays.
a. Describe how to perform the SEARCH operation for this data structure. Analyze its worst-case running time.
b. Describe how to insert a new element into this data structure. Analyze its worst-case and amortized running times.
c. Discuss how to implement DELETE.