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

Recall & Review

beginner

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

Binary search is much faster because it cuts the search space in half each time, making it efficient for large sorted lists.

beginner

Why must the list be sorted for binary search to work?

Because binary search compares the target with the middle element and decides which half to search next, the list must be sorted to know which half contains the target.

beginner

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

Sorted order means the elements are arranged from smallest to largest (or vice versa), so you can predict where to find elements based on comparisons.

intermediate

How does binary search reduce the number of comparisons compared to linear search?

Binary search divides the list in half each time, so it only needs about log₂(n) comparisons, while linear search may need up to n comparisons.

beginner

What happens if you try to use binary search on an unsorted list?

Binary search will not work correctly because the assumption about sorted order is broken, leading to wrong decisions about which half to search.

Why is a sorted list necessary for binary search?

A To avoid duplicates

B To make the list shorter

C To decide which half of the list to search next

D To use less memory

Binary search relies on sorted order to know if the target is in the left or right half after comparing with the middle element.

What is the time complexity of binary search in terms of number of elements n?

A O(log n)

B O(1)

C O(n log n)

D O(n)

Binary search cuts the search space in half each step, so it runs in logarithmic time O(log n).

If a list is not sorted, what will happen if you use binary search?

A It will sort the list first

B It will always find the target

C It will find the target faster

D It may give wrong results

Binary search assumes sorted order; without it, the search decisions are invalid and results can be wrong.

Which of these is a benefit of sorted order besides binary search?

A Slower insertion

B Easier to find minimum and maximum

C More memory usage

D No duplicates allowed

In a sorted list, the first element is the minimum and the last is the maximum, making them easy to find.

How many elements remain to search after the first step of binary search on a list of 16 elements?

A 8

B 15

C 4

D 1

Binary search splits the list in half, so after one step, only 8 elements remain to search.

Explain why binary search requires a sorted list and how it uses this property to find an element.

Think about how knowing order helps decide where to look next.

Describe the difference in efficiency between linear search and binary search and why binary search is faster on large sorted lists.

Consider how many steps each method takes as the list grows.