Binary Search vs Linear Search Real Cost Difference in DSA Javascript - Key Differences

Recall & Review

beginner

What is the main difference between linear search and binary search?

Linear search checks each item one by one until it finds the target or reaches the end. Binary search splits the list in half repeatedly to find the target faster but requires the list to be sorted.

beginner

Why does binary search require a sorted list?

Binary search depends on comparing the middle item to the target to decide which half to search next. If the list is not sorted, this logic breaks and the search won't work correctly.

intermediate

What is the time complexity of linear search and binary search?

Linear search has a time complexity of O(n), meaning it may check every item. Binary search has a time complexity of O(log n), meaning it cuts the search space in half each step, making it much faster on large lists.

intermediate

In what situation might linear search be better than binary search?

If the list is small or unsorted, linear search can be simpler and faster because binary search requires sorting first, which takes extra time.

beginner

Explain the real cost difference between binary search and linear search in simple terms.

Linear search looks at each item one by one, so it can be slow if the list is big. Binary search quickly jumps to the middle and cuts the list in half each time, so it finds things much faster but only if the list is sorted.

Which search method requires the list to be sorted?

A Binary Search

B Linear Search

C Both

D Neither

Binary search only works correctly if the list is sorted because it decides which half to search based on comparisons.

What is the worst-case time complexity of linear search?

A O(n)

B O(1)

C O(n log n)

D O(log n)

Linear search may need to check every item, so its worst-case time is O(n).

How does binary search reduce the search space each step?

A By removing all items except one

B By removing one item

C By removing a quarter of the items

D By removing half the items

Binary search cuts the list in half each time, quickly narrowing down where the target can be.

When might linear search be preferred over binary search?

A When the list is very large and sorted

B When the list is sorted and large

C When the list is small or unsorted

D Never

Linear search is simple and works on unsorted lists, so it can be better for small or unsorted data.

Which search is generally faster on large sorted lists?

A Linear Search

B Binary Search

C Both are the same

D Depends on the data

Binary search is much faster on large sorted lists because it reduces the search space quickly.

Describe how binary search works and why it is faster than linear search on sorted lists.

Think about cutting the search area in half each time.

Explain when you would choose linear search over binary search and why.

Consider the cost of sorting and list size.