Why Binary Search and What Sorted Order Gives You in DSA C++ - Quick Recap

Recall & Review

beginner

What is the main advantage of using binary search over linear search?

Binary search is much faster because it repeatedly divides the search space in half, reducing the number of comparisons from linear (n) to logarithmic (log n).

beginner

Why must the data be sorted to use binary search?

Binary search relies on the data being sorted so it can decide which half of the data to ignore after each comparison, ensuring the search space shrinks correctly.

beginner

What does 'sorted order' mean in the context of binary search?

Sorted order means the elements are arranged in increasing or decreasing order, so each element is in a predictable position relative to others.

intermediate

How does sorted order help in reducing the search time?

Sorted order allows binary search to eliminate half of the remaining elements after each comparison, quickly narrowing down the possible location of the target.

intermediate

What is the time complexity of binary search and why?

The time complexity is O(log n) because the search space is halved with each step, leading to a logarithmic number of steps relative to the number of elements.

Why can binary search only be used on sorted data?

A Because it needs to know which half to discard after each comparison

B Because it compares every element one by one

C Because it works only on numbers

D Because it requires data to be in random order

Binary search decides which half to ignore based on the order, so data must be sorted.

What happens to the search space after each step in binary search?

A It doubles

B It stays the same

C It halves

D It becomes empty

Binary search halves the search space after each comparison.

What is the best case time complexity of binary search?

A O(log n)

B O(1)

C O(n)

D O(n log n)

If the target is found at the middle element immediately, the time is O(1).

Which of these is NOT a requirement for binary search?

A Data must be sorted

B Data must be in an array or list

C Data must allow random access

D Data must be unique

Data does not need to be unique for binary search to work.

If you have 1,000,000 sorted elements, about how many steps does binary search take in the worst case?

A 20

B 1,000,000

C 100

D 10,000

Binary search takes about log2(1,000,000) ≈ 20 steps.

Explain why sorted order is essential for binary search and how it helps reduce search time.

Think about how knowing order helps decide which part to ignore.

Describe the step-by-step process of binary search on a sorted list.

Imagine looking for a word in a dictionary.