Exponential Search – Multiple Choice Questions and Answers (MCQs)

Data Structures & Algorithms Computer Science & Engineering

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

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

Explanation: For finding the element being searched, exponential search does not require any additional space. As a result, it still has auxiliary space O. (1).

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

Explanation: When used with recursive binary search, exponential search requires an auxiliary space of log n. The recursion call stack space requires this space.

3. Which of the following searching algorithm is fastest?
A) jump search
B) exponential search
C) linear search
D) all are equally fast

Explanation: Out of the available searching algorithms, exponential search has the shortest time complexity (log n). In most instances, exponential search is preferable.

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

Explanation: An exponential search will leap backwards up to log n times, while a jump search can only go backwards once. If jumping backwards is costly, jump quest would be preferred.

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

Explanation: When the first element of the sequence is the element being searched, the exponential search performs best. Only one comparison will be needed in this case. As a result, it will have an O time complexity (1).

6. 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
}


Explanation: We first find a range in the array where the appropriate element should be present in exponential search. Then, in this range, we use binary search.

7. Jump search has a better time complexity than the exponential search.
A) True
B) False

Explanation: Jump and exponential searches have worst-case time complexity of O(n1/2) and O(log n), respectively. In terms of time complexity, exponential search is superior.

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

Explanation: Exponential search identifies the range in which binary search should be used first. As a result, exponential search outperforms standard binary search when the element is near the array’s start point.

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

Explanation: Exponential and binary search have the same time complexity. When the element being searched is near the array’s start point, however, exponential search outperforms binary search.

10. Which of the following is not an alternate name of exponential search?
A) Logarithmic search
B) Doubling search
C) Galloping search
D) Struzik search

Explanation: The exponential search is not known by the term logarithmic search. Doubling quest, Galloping search, and Struzik search are some of the other names for exponential search.

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

Explanation: The input array must be sorted for exponential sort to work. If the array is not sorted, the algorithm will fail to produce the desired result.

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

Explanation: We first find a range in the array where the necessary elements should be present in exponential search. Then, in this range, we use binary search.

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

Explanation: There is no exponential space complexity or exponential time complexity in exponential quest. Since it searches for an element in an exponential way, it is called exponential search.

14. 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; 

C)

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

D)

while (i < n)  
        i = i*2; 


Explanation: Before using binary search, we use exponential search to find the range in which the element being searched can be found. We do this by comparing the value of the searched element to the array elements at positions 1,2,4,8,…. n.

15. What is the time complexity of exponential sort?
A) O(n)
B) O(2n)
C) O(n log n)
D) O(log n)

Explanation: We first find a range in the array where the necessary elements should be present in exponential search. Then, in this range, we use binary search. In the worst-case scenario, this takes O(log n) time.

In computer science, an exponential search (also known as doubling search, galloping search, or Struzik search) is an algorithm for searching sorted, unbounded/infinite lists that was developed by Jon Bentley and Andrew Chi-Chih Yao in 1976. There are many approaches to this, the most common of which is to define a range in which the search key exists and then perform a binary search within that range. This takes O(log I where I is the location of the search key in the list if it exists, or the position where the search key should be if it does not.

Leave a Reply

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