Binary Search MCQ - Sanfoundry

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

1. What is the advantage of recursive approach than an iterative approach?
a) Consumes less memory
b) Less code and easy to implement
c) Consumes more memory
d) More code has to be written
View Answer

Answer: b
Explanation: A recursive approach is easier to understand and contains fewer lines of code.

2. Choose the appropriate code that does binary search using recursion.
a)

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + (high - low)/2;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid+1,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + (high + low)/2;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid-1,high,key);
	}
	else
	{
		return recursive(arr,low,mid+1,key);
	}
}

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + (high - low)/2;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

public static int recursive(int arr[], int low, int high, int key)
{
	int mid = low + ((high - low)/2)+1;
	if(arr[mid] == key)
	{
		return mid;
	}
	else if(arr[mid] < key)
	{
		return recursive(arr,mid,high,key);
	}
	else
	{
		return recursive(arr,low,mid-1,key);
	}
}

View Answer

Answer: a
Explanation: Calculate the ‘mid’ value, and check if that is the key, if not, call the function again with 2 sub arrays, one with till mid-1 and the other starting from mid+1.

3. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
a) 5
b) 2
c) 3
d) 4
View Answer

Answer: c
Explanation: level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).

4. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
a) 90 and 99
b) 90 and 94
c) 89 and 99
d) 89 and 94
View Answer

Answer: a
Explanation: At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.

5. What is the worst case complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
View Answer

Answer: b
Explanation: Using the divide and conquer master theorem.

6. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
View Answer

Answer: b
Explanation: T(n) = T(n/2) + 1, Using the divide and conquer master theorem.

7. Which of the following is not an application of binary search?
a) To find the lower/upper bound in an ordered sequence
b) Union of intervals
c) Debugging
d) To search in unordered list
View Answer

Answer: d
Explanation: In Binary search, the elements in the list should be sorted. It is applicable only for ordered list. Hence Binary search in unordered list is not an application.

8. Choose among the following code for an iterative binary search.
a)

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high + low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid - 1;
		}
		else
		{
			high = mid + 1;
		}
	}
	return -1;
}

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high - low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high + low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}
	return -1;
}

public static int iterative(int arr[], int key)
{
	int low = 0;
	int mid = 0;
	int high = arr.length-1;
	while(low <= high)
	{
		mid = low + (high - low)/2;
		if(arr[mid] == key)
		{
			return mid;
		}
		else if(arr[mid] < key)
		{
			low = mid - 1;
		}
		else
		{
			high = mid + 1;
		}
	}
	return -1;
}

View Answer

Answer: b
Explanation: Find the ‘mid’, check if it equals the key, if not, continue the iterations until low <= high.

9. Binary Search can be categorized into which of the following?
a) Brute Force technique
b) Divide and conquer
c) Greedy algorithm
d) Dynamic programming
View Answer

Answer: b
Explanation: Since ‘mid’ is calculated for every iteration or recursion, we are diving the array into half and then try to solve the problem.

10. Given an array arr = {5,6,77,88,99} and key = 88; How many iterations are done until the element is found?
a) 1
b) 3
c) 4
d) 2
View Answer

Answer: d
Explanation: Iteration1 : mid = 77; Iteration2 : mid = 88;

11. Given an array arr = {45,77,89,90,94,99,100} and key = 100; What are the mid values(corresponding array elements) generated in the first and second iterations?
a) 90 and 99
b) 90 and 100
c) 89 and 94
d) 94 and 99
View Answer

Answer: a
Explanation: Trace the input with the binary search iterative code.

12. What is the time complexity of binary search with iteration?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n²)
View Answer

Answer: b
Explanation: T(n) = T(n/2) + theta(1)
Using the divide and conquer master theorem, we get the time complexity as O(logn).

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]

« Prev - Linear Search Recursive Multiple Choice Questions and Answers (MCQs)

» Next - Data Structure Questions and Answers – Uniform Binary Search

Related Posts:

Recommended Articles: