# Question: Binary search of a sorted array takes logarithmic search

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.

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.

## Answer to relevant Questions

There are four basic operations on red-black trees that perform structural modifications: node insertions, node deletions, rotations, and color modifications. We have seen that RB-INSERT and RB-DELETE use only O (1) ...Suppose that you are given an n × n checkerboard and a checker. You must move the checker from the bottom edge of the board to the top edge of the board according to the following rule. At each step you may move the checker ...Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations on his route. The ...The incidence matrix of a directed graph G = (V, E) is a |V| × |E| matrix B = (bij) such thatDescribe what the entries of the matrix product B BT represent, where BT is the transpose of B.Explain the following in you own words:Coercion pseudo variableGenerated type selectorLiteral strong typing Ordinal type The-operatorPolymorphic operator type generatorPost your question