Binary Search Iterative – Data Structure Questions and Answers

Data Structures & Algorithms Computer Science & Engineering

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

1. What is the average case time complexity of binary search using recursion?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

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

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

Explanation: The elements in the list should be sorted in Binary search. It is only applicable to organised lists. As a result, binary search in an unordered list is not a useful tool.

3. 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;
}

B)

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;
}

C)

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;
}

D)

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;
}


Explanation: Find the ‘mid’ and see if it equals the key; if not, keep going until low = high.

4. Binary Search can be categorized into which of the following?
A) Brute Force technique
B) Divide and conquer
C) Greedy algorithm
D) Dynamic programming

Explanation: We split the array in half and then try to solve the problem since ‘mid’ is computed for each iteration or recursion.

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

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

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

Explanation: Use the binary search iterative code to trace the input.

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

Explanation: T(n) = T(n/2) + theta(1)
We get the time complexity as O using the divide and conquer master theorem (logn).

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

Explanation: A recursive approach is more straightforward to comprehend and uses fewer lines of code.

9. 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);
	}
}

B)

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);
	}
}

C)

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);
	}
}

D)advertisement

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);
	}
}


Explanation: Calculate the ‘mid’ value and see if it is the key; if it isn’t, call the function again with two sub arrays, one starting at mid-1 and the other at mid+1.

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

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

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

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

12. What is the worst case complexity of binary search using recursion?
A) O(nlogn)
B) O(logn)
C) O(n)
D) O(n2)

Explanation: Using the master theorem of divide and conquer.

The binary search algorithm has an O time complexity (log n). When the central index explicitly matches the desired value, the best-case time complexity is O(1). The values at either end of the list, or values not on the list, may be the worst-case scenario. Using a recursive binary search function, I’d go for a recursive increment. Simply increment by one in each branch of the binary tests, and the iterations will be counted recursively. Binary search, like all divide-and-conquer algorithms, divides a large array into two smaller subarrays and then operates on the subarrays recursively (or iteratively).

Leave a Reply

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