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(n

^{2})

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

publicstaticintiterative(intarr[],intkey) {intlow = 0;intmid = 0;inthigh = arr.length-1;while(low <= high) { mid = low + (high + low)/2;if(arr[mid] == key) {returnmid; }elseif(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)

publicstaticintiterative(intarr[],intkey) {intlow = 0;intmid = 0;inthigh = arr.length-1;while(low <= high) { mid = low + (high + low)/2;if(arr[mid] == key) {returnmid; }elseif(arr[mid] < key) { low = mid + 1; }else{ high = mid - 1; } }return-1; }

D)

publicstaticintiterative(intarr[],intkey) {intlow = 0;intmid = 0;inthigh = arr.length-1;while(low <= high) { mid = low + (high - low)/2;if(arr[mid] == key) {returnmid; }elseif(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(n^{2})**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)

publicstaticintrecursive(intarr[],intlow,inthigh,intkey) {intmid = low + (high + low)/2;if(arr[mid] == key) {returnmid; }elseif(arr[mid] < key) {returnrecursive(arr,mid-1,high,key); }else{returnrecursive(arr,low,mid+1,key); } }

C)

publicstaticintrecursive(intarr[],intlow,inthigh,intkey) {intmid = low + (high - low)/2;if(arr[mid] == key) {returnmid; }elseif(arr[mid] < key) {returnrecursive(arr,mid,high,key); }else{returnrecursive(arr,low,mid-1,key); } }

D)advertisement

publicstaticintrecursive(intarr[],intlow,inthigh,intkey) {intmid = low + ((high - low)/2)+1;if(arr[mid] == key) {returnmid; }elseif(arr[mid] < key) {returnrecursive(arr,mid,high,key); }else{returnrecursive(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(n^{2})**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).