Searching algorithms (linear, binary) in Intro to Computing - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a linear search algorithm?

Linear search is a method of finding a target value by checking each element in a list one by one from start to end until the target is found or the list ends.

beginner

What condition must be true for binary search to work?

The list must be sorted in order (either ascending or descending) before performing a binary search.

intermediate

How does binary search reduce the search area?

Binary search compares the target with the middle element of the list. If the target is smaller, it searches the left half; if larger, it searches the right half. This halves the search area each time.

beginner

Which search algorithm is faster for large sorted lists: linear or binary search?

Binary search is faster for large sorted lists because it reduces the search area by half each step, while linear search checks elements one by one.

intermediate

Explain the worst-case time complexity of linear and binary search.

Linear search worst-case time is O(n), meaning it may check every element. Binary search worst-case time is O(log n), meaning it divides the search area repeatedly, making it much faster on large lists.

Which search algorithm requires the list to be sorted?

A Neither linear nor binary search

B Linear search

C Binary search

D Both linear and binary search

Binary search only works correctly if the list is sorted. Linear search works on any list.

In linear search, what happens if the target is not in the list?

A The algorithm stops immediately

B The algorithm stops after checking half the elements

C The algorithm sorts the list first

D The algorithm stops after checking all elements

Linear search checks each element until the end if the target is not found.

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

A It works on unsorted lists

B It is faster on large sorted lists

C It uses less memory

D It is easier to implement

Binary search is faster on large sorted lists because it halves the search area each step.

If a list has 16 elements, how many steps does binary search take in the worst case?

A 4 steps

B 8 steps

C 16 steps

D 1 step

Binary search takes log2(16) = 4 steps in the worst case.

Which search algorithm checks elements one by one?

A Linear search

B Binary search

C Both

D None

Linear search checks each element one by one until it finds the target or reaches the end.

Describe how linear search works using a real-life example.

Think about looking for a book on a messy shelf.

Explain the steps of binary search and why the list must be sorted.

Imagine searching for a word in a dictionary.