CPSC 121 Lecture Notes - Lecture 16: Binary Search Algorithm

• School: UBC
• Department: Computer Science
• Course: CPSC 121
• Professor: Frederick Shepherd

Document Summary

, () - at least one x. To write there is exactly one x d w/ property p. There is exactly one x d w/ property p. There exists mean there is at least one. Given: a sorted list of names w/ phone numbers. L: check the first name, if it"s not n, the check the second name, the check the third name, etc. B: check the name in the middle of the list. If n comes earlier alphabetically the search the first half of the list using b. If it comes later search the second half of the list instead. Repeat until you have found n or you"re looking at an empty sub list (aka binary search) L takes n steps where phone book has names. B = binary search takes at most t (n) steps=rips. {how do we determine whether or not an algorithm is generally faster than another?}