Data Structure Questions and Answers – Uniform Binary Search

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

1. 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
View Answer

Answer: d
Explanation: Uniform binary search code is more complex to implement than binary search as it involves mid points to be computed in hand before search.

2. 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)

advertisement
advertisement
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)

Note: Join free Sanfoundry classes at Telegram or Youtube
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)

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);
}
View Answer
Answer: a
Explanation: This provides a single lookup index and the values are dependent on the the number of elements(N) in the array.

3. 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
View Answer

Answer: b
Explanation: Trace with respect to the make_delta function, always note that the last element is always 0.
advertisement

4. 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];
            }
       }
}
View Answer
Answer: c
Explanation: Unlike the usual binary search which a low, high and a mid variable and every time comparing the key with the mid value, the comparing index is obtained from the lookup delta table, choosing the left or right side of the array is same as with the normal binary search.
 
 

5. What is the time complexity of uniform binary search?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
View Answer

Answer: b
Explanation: With every iteration we are dividing the array into two parts(though not equal halves), the complexity remains same as the normal binary search.

6. 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
View Answer

Answer: b
Explanation: Tracing with the above code, comparison #1: i=4, comparison #2: i=7, comparison #3: i=8

7. 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)
View Answer

Answer: b
Explanation: This gives a very slight improvement as you are skipping the first k elements.

8. 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
View Answer

Answer: d
Explanation: Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won’t start searching from index 0.

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.