CP104 Lecture Notes - Lecture 2: Linear Search, Binary Search Algorithm, Auxiliary Memory
CP104 verified notes
2/3View all
Document Summary
Starting at the beginning of the list, look at each element one by one in the list and compare if to the number you are trying to find. Stop when you have found the matching number or have reached the end of the list. This is called a linear search: assuming the elements of the list are in order , split the list in two. If the number you are looking for matches the number in the middle, stop/ if the middle is greater than the number, repeat in the left half of the list. If the middle is less than the number, repeat in the right half of the list/ stop when you have found the matching number or when you can no longer split the list in half. This is called a binary search. (we will see more of both of these algorithms later!)