Searching finds an item in a list and sorting puts a list in order. This lesson explains linear search and binary search and why binary search needs a sorted list, then works through bubble sort and insertion sort, including how many passes each takes and how a list looks part way through.
Slide 1 / 4
Linear search
A linear search checks each item in the list in turn, from the first to the last, until it finds the item it is looking for or reaches the end.
It works on any list, whether the data is sorted or not, which makes it simple and always usable.
In the worst case the item is last or not present, so a linear search of n items may need up to n comparisons.
Linear search is easy to write but slow on large lists, because on average it must check about half of the items.
Check you've got it
0/4
1. What must be true about a list before a binary search can be used on it?
2. The list 5, 3, 8, 1 is sorted into ascending order using a bubble sort. What is the list after ONE complete pass?
3. Which statement about linear search and binary search is correct?
4. How does an insertion sort place each new item into the sorted part of the list?