1.6 Linear Search and Binary Search

8.24.26 Class Review

What does Linear Search do?

It checks elements one at a time until it finds the desired value or reaches the end.

What is the runtime complexity of Linear Search?

O(N)

What is the best case for Linear Search?

The key is the first element

What is the worst case for Linear Search?

The key is not found or is at the last position, requiring all elements to be checked.

If Linear Search finds the key in the middle of the array, is that best or worst?

Neither

Why is Linear Search O(N)?

In the worst case, it may have to check all N elements.

What is a Binary Search?

A search algorithm that repeatedly divides the search area in half.

What is required for Binary Search?

The data must be ordered/sorted.

What is the runtime complexity of Binary Search?

O(log N)

Why is Binary Search faster than Linear Search for large inputs?

It eliminates about half of the remaining search area after each comparison.

What is the major difference between Linear Search and Binary Search?

Linear Search checks items one at a time; Binary Search repeatedly cuts the the search area in half.

What is the key requirement that Linear Search does not have?

Binary Search requires the data to be sorted.