Introduction to Computer Science II CS112-2008S-33 Binary Search & Trees David Galles Department of Computer Science University of San Francisco 33-0: Sorting Review: Insertion Sort Selection Sort 33-1: Sorted Lists Maintain a sorted list: Add an element Determine if an element is in the list Print out the list in order Array vs. Linked List 33-2: Sorted Lists Array Finding an element is fast Inserting an element is slow 33-3: Sorted Lists Array Finding an element is fast Binary Search O(lgn) Inserting an element is slow Move larger elements one to the right O(n) 33-4: Binary Search If we are looking for an element in an empy list, return false If the element in the center of the list is what we are looking for, return true If the element in the center of the list is less that what we are looking for, discard the left half of the list, continue looking If the element in the center of the list is greater than what we are looking for, discard the right half of the list, co...