Binary Search Algorithm Questions

Mahesh pal

Score: 🔥 44

Beginner

Took 2 months

DSA

Binary Search Algorithm

66%

Questions Attempted

15 / 15

Correct Answers

Incorrect Answers

Points Earned

🔥 10

Question 1

In terms of space complexity, how does the iterative binary search compare to the recursive one?

Iterative binary search generally uses less space.
Recursive binary search generally uses less space.
Both have the same space complexity.
It depends on the size of the input array.

Explanation:

Recursive calls in binary search incur function call overhead, potentially leading to higher space usage than an iterative approach.

Question 2

In what scenario would linear search be more suitable than binary search?

Searching for a specific value in a sorted array.
Finding the smallest element in a rotated sorted array.
Searching for an element in a small, unsorted array.
Finding the median value in a sorted array.

Explanation:

For very small datasets or unsorted data, the overhead of sorting for binary search might outweigh its benefits. Linear search, while generally slower, can be more efficient in these specific cases.

Question 3

What is the time complexity of Binary Search in the best-case scenario?

O(n)
O(log n)
O(1)
O(n log n)

Explanation:

In the best case, the target element is found in the middle of the array on the first comparison, resulting in constant time.

Question 4

You have an unsorted array, and you need to find a specific value. Is it more efficient to sort the array and then use binary search, or to directly apply linear search?

Sort and then use binary search
Directly use linear search

Explanation:

Sorting an array itself generally has a time complexity of O(n log n). If you only need to find one value, linear search's O(n) complexity is more efficient than sorting followed by binary search.

Question 5

In binary search, what happens if the target value is less than the middle element of the current search interval?

The search continues in the left half of the interval.
The search continues in the right half of the interval.
The search terminates as the target is not found.
The middle element is compared with its adjacent elements.

Explanation:

Since the array is sorted, if the target is less than the middle, it must reside in the left portion.

Question 6

What is the time complexity of Binary Search in the worst-case scenario?

O(n)
O(log n)
O(1)
O(n log n)

Explanation:

Binary Search halves the search space in each step, leading to a logarithmic time complexity. In the worst case, we perform log n comparisons.

Question 7

What happens if the target element is not present in the array during Binary Search?

It returns the index where the element should be inserted.
It returns -1.
It throws an exception.
It enters an infinite loop.

Explanation:

By convention, Binary Search returns -1 to indicate that the target element was not found in the array.

Question 8

How does Binary Search handle duplicate elements in a sorted array?

It returns the index of any one occurrence of the target element.
It returns the index of the first occurrence of the target element.
It returns the index of the last occurrence of the target element.
It throws an error as Binary Search requires unique elements.

Explanation:

The standard Binary Search algorithm does not guarantee which occurrence's index will be returned if duplicates exist.

Question 9

What value does binary search return if the target element is not present in the sorted array?

-1
Index where the element should be inserted
Null
It depends on the implementation

Explanation:

There is no single standard. Some implementations return -1, others might return the index where the element would be if inserted, and others might use a different convention.

Question 10

Which of the following best describes the advantage of binary search over linear search?

Binary search uses less memory.
Binary search is easier to implement.
Binary search has a faster average-case time complexity.
Binary search can be used on unsorted data.

Explanation:

The primary advantage of binary search is its efficiency. It outperforms linear search in the average and worst-case scenarios due to its logarithmic time complexity, especially for larger datasets.

Question 11

What is the key characteristic of an array that makes Binary Search applicable?

The array must be sorted.
The array must be of a fixed size.
The array must contain only positive integers.
The array must be stored in contiguous memory locations.

Explanation:

Binary Search fundamentally relies on the array being sorted. It repeatedly divides the search interval in half, which is only efficient and correct if the array is sorted.

Question 12

Which of the following is a prerequisite for using binary search on a dataset?

The data must be sorted.
The data must be stored in a linked list.
The data must contain only numerical values.
The data must be stored in a hash table.

Explanation:

Binary search relies on the data being sorted to repeatedly narrow down the search interval. Without a sorted dataset, you cannot effectively determine which half to discard in each step.

Question 13

What is the base case in a recursive implementation of binary search?

When the target element is found.
When the search interval becomes empty.
When the middle element equals the target element.
Both option1 and option2

Explanation:

The base case signals the end of recursion. In binary search, it occurs when either the target is found or the interval is empty, indicating the target's absence.

Question 14

Which of the following best describes the time complexity of binary search in the average case?

O(n)
O(log n)
O(n log n)
O(1)

Explanation:

Binary search halves the search space with each step, resulting in a logarithmic time complexity.

Question 15

In the context of Binary Search, what is the problem with searching in an infinitely sized array?

Binary Search cannot handle arrays with no defined end.
Binary Search requires the entire array to be loaded into memory.
Binary Search is too slow for infinitely sized arrays.
Binary Search cannot handle duplicate elements in an infinitely sized array.

Explanation:

Standard Binary Search requires a defined search space with a start and an end. Infinite arrays lack this defined end, making the classic algorithm inapplicable.