Uniform Binary Search – Data Structure Questions and Answers

Data Structures & Algorithms Computer Science & Engineering

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Uniform Binary Search”.

1. Choose the appropriate code snippet that performs uniform binary search.
A)

public static int unisearch(int key) 
{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i += delta[++j];
                else
                    i -= delta[++j];
            }
       }
}

B)

public static int unisearch(int key) 
{
       int i = delta[1] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i -= delta[++j];
                else
                    i += delta[++j];
            }
       }
}

C)

public static int unisearch(int key) 
{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i -= delta[++j];
                else
                    i += delta[++j];
            }
       }
}

d)

public static int unisearch(int key) 
{
       int i = delta[0] - 1; 
       int j = 0;
       while (true) 
       {
            if (key == arr[i])
                return i;
            else if (delta[j] == 0)
                return -1;
            else 
            {
                if (key < arr[i])
                    i += delta[++j];
                else
                    i += delta[++j];
            }
       }
}

Explanation: Unlike the traditional binary search, which uses a low, high, and mid variable and compares the key to the mid value every time, the comparing index is derived from the lookup delta table, and the left or right side of the list is chosen in the same way as the traditional binary search.

2. What is the time complexity of uniform binary search?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: We divide the array into two sections (though not identical halves) for each iteration, and the complexity remains the same as a standard binary search.

3. Given, arr = {1,3,5,6,7,9,14,15,17,19} key = 17 and delta = {5,3,1,0}
How many key comparisons are made?(exclude the comparison used to decide the left or right sub array)

A) 4
B) 3
C) 5
D) 6

Explanation: Using the above code, the first relation is i=4, the second is i=7, and the third is i=8.

4. How can Jump Search be improved?
A) Start searching from the end
B) Begin from the kth item, where k is the step size
C) Cannot be improved
D) Step size should be other than sqrt(n)

Explanation: Since the first k elements are skipped, this results in a very slight change.

5. Which of the following false about Jump Search?
A) Jump Search is better than Linear Search
B) Useful when jumping back is more costly than jumping forward
C) Jump Search is worse than Binary Search
D) Jump search starts from the index 0 even though specified index is k

Explanation: Linear search is O(n) complex, while Binary search is O(logn). Since you only have to jump backwards once in Jump search, it is better if jumping backwards is expensive. Jump search begins at index k (specified index) and continues until the element is found. It will not begin searching at index 0.

6. In which of the cases uniform binary search fails compared to binary search?
A) A table lookup is generally faster than an addition and a shift
B) Many searches will be performed on the same array
C) Many searches will be performed on several arrays of the same length
D) Complexity of code

Explanation: Uniform binary search code is more difficult to implement than binary search because it requires hand computation of mid points before searching.

7. Which of the following is a suitable lookup table that can be used in the uniform binary search?(N is the number of elements in the array and the delta array is global)
A)

public static void make_delta(int N) 
{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
       } 
       while (delta[i++] != 0);
}

B)

public static void make_delta(int N) 
{
       int power = 0;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N + half) / power;
       } 
       while (delta[i++] != 0);
}

C)advertisement

public static void make_delta(int N) 
{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power >>= 1;
            delta[i] = (N + half) / power;
       }
       while (delta[i++] != 0);
}

D)

public static void make_delta(int N) 
{
       int power = 1;
       int i = 0;
       do 
       {
            int half = power;
            power <<= 1;
            delta[i] = (N - half) / power;
       } 
       while (delta[i++] != 0);
}


Explanation: This creates a single lookup index, and the values are determined by the array’s number of elements (N).

8. Given delta[4] is a global array and number of elements in the sorted array is 10, what are the values in the delta array?
A) 4, 3, 1, 0
B) 5, 3, 1, 0
C) 4, 2, 1, 1
D) 5, 2, 1, 1

Explanation: When tracing the make delta function, keep in mind that the last element is always 0.

When many searches are performed on the same array or many arrays of the same size, Uniform Binary Search is an optimization of the Binary Search algorithm. To find the midpoints in a traditional binary search, we use arithmetic operations. Here, we calculate midpoints ahead of time and enter them into a lookup table. To find the midpoint, array look-up is usually faster than arithmetic (addition and shift). The method is very similar to the Binary Search algorithm, with the exception that an array is generated and the lookup table is used to change the index of the pointer in the array, making the search faster.

Leave a Reply

Your email address will not be published. Required fields are marked *