# Exponential Search Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Exponential Search”.

1. Exponential search algorithm requires which of the following condition to be true?
a) array should be sorted
b) array should have not be sorted
c) array should have a less than 128 elements
d) array should be partially sorted
View Answer

Answer: a
Explanation: Exponential sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.

2. Which of the following searching algorithm is used with exponential sort after finding the appropriate range?
a) Linear search
b) Binary search
c) Jump search
d) Fibonacci Search
View Answer

Answer: b
Explanation: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.

3. Exponential search has ____________
a) neither an exponential space complexity nor exponential time complexity
b) exponential time complexity but a linear space complexity
c) exponential space complexity but a linear time complexity
d) both exponential time and space complexity
View Answer

Answer: a
Explanation: Exponential search has neither an exponential space complexity nor exponential time complexity. It is named exponential search because it searches for an element in an exponential manner.
advertisement
advertisement

4. Choose the correct while loop statement from the following that finds the range where are the element being search is present (x is the element being searched in an array arr of size n)?
a)

```while (i < n && arr[i] <= x)
i = i*2; ```

b)

```while (i < n && arr[i] <= x)
i = i/2; ```
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

c)

```while (arr[i] <= x)
i = i/2; ```

d)

```while (i < n)
i = i*2; ```
View Answer
Answer: a
Explanation: In exponential search we first find the range where the element being searched can be present before applying binary search. We do this by comparing the value of element under search with the array elements present at the positions 1,2,4,8….n.

advertisement

5. What is the time complexity of exponential sort?
a) O(n)
b) O(2n)
c) O(n log n)
d) O(log n)
View Answer

Answer: d
Explanation: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range. This takes O(log n) time in the worst case.

6. What is the auxiliary space requirement of an exponential sort when used with iterative binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
View Answer

Answer: c
Explanation: Exponential search does not require any auxiliary space for finding the element being searched. So it has a constant auxiliary space O(1).
advertisement

7. What is the auxiliary space requirement of the exponential sort when used with recursive binary search?
a) O(n)
b) O(2n)
c) O(1)
d) O(log n)
View Answer

Answer: d
Explanation: Exponential search requires an auxiliary space of log n when used with recursive binary search. This space is required for the recursion call stack space.

8. Which of the following searching algorithm is fastest?
a) jump search
b) exponential search
c) linear search
d) all are equally fast
View Answer

Answer: b
Explanation: Exponential search has the least time complexity (equal to log n) out of the given searching algorithms. This makes exponential search preferable in most cases.

9. In which of the following case jump search will be preferred over exponential search?
a) jumping backwards takes significantly more time than jumping forward
b) jumping forward takes significantly more time than jumping backwards
c) when the given array is very large in size
d) when the given array is very small in size
View Answer

Answer: a
Explanation: Jump search only needs to jump backwards once, while an exponential search can jump backwards up to log n times. Thus jump search will be preferred if jumping backwards is expensive.

10. Best case of the exponential search will have time complexity of?
a) O(1)
b) O(n)
c) O(log n)
d) O(n log n)
View Answer

Answer: a
Explanation: Best case of the exponential search will be when the first element of the array is the element that is being searched. In this case, only one comparison will be required. Thus it will have a time complexity of O(1).

11. Which of the following code correctly represent exponential search?
a)

```int expSearch(int arr[], int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;

return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}```

b)

```int expSearch(int arr[], int n, int x)
{
if (arr[0] == x)
return 0;
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
return binarySearch(arr, i, min(i, n-1), x);
//applies binary search in the calculated range
}```

c)

```int expSearch(int arr[], int n, int x)
{

if (arr[0] == x)
return 0;

int i = 1;
while (i < n && arr[i] <= x)
i = i/2;

return binarySearch(arr, i/2, min(i, n-1), x);
//applies binary search in the calculated range
}```

d)

```int expSearch(int arr[], int n, int x)
{
if (arr[0] == x)
return 0;

int i = 1;
while (i < n && arr[i] <= x)
i = i*2;

return binarySearch(arr, i/2, max(i, n-1), x);
//applies binary search in the calculated range
}```
View Answer
Answer: a
Explanation: In exponential search we first find a range where the required element should be present in the array. Then we apply binary search in this range.

12. Jump search has a better time complexity than the exponential search.
a) True
b) False
View Answer

Answer: b
Explanation: The worst case time complexity of jump search and exponential searches are O(n1/2) and O(log n) respectively. So exponential search is better in terms of time complexity.

13. Exponential search performs better than binary search when the element being searched is present near the starting point of the array.
a) True
b) False
View Answer

Answer: a
Explanation: Exponential search first finds the range where binary search needs to be applied. So when the element is present near the starting point of the array then exponential search performs better than standard binary search.

14. Choose the incorrect statement about exponential search from the following.
a) Exponential search is an in place algorithm
b) Exponential search has a greater time complexity than binary search
c) Exponential search performs better than binary search when the element being searched is present near the starting point of the array
d) Jump search has a greater time complexity than an exponential search
View Answer

Answer: b
Explanation: Time complexity of exponential search and binary search are the same. But exponential search performs better than binary search when the element being searched is present near the starting point of the array.

15. Which of the following is not an alternate name of exponential search?
a) Logarithmic search
b) Doubling search
c) Galloping search
d) Struzik search
View Answer

Answer: a
Explanation: Logarithmic search is not an alternate name of the exponential search. Some alternate names of exponential search are Doubling search, Galloping search and Struzik search.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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, 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.