# Lecture Notes for CS 112 - Intro to Computer Science II at University of San Francisco (USF)

## Notes Information

 Material Type: Class Note Professor: Staff Class: CS 112 - Intro to Computer Science II Subject: Computer Science University: University of San Francisco (CA) Term: 2008 Keywords: Binary SearchOn the RightOn the LeftRoot ElementImmediatelyOriginal ProblemBinary Search TreeComputer Science IiLinked ListIn Front Of

## Sample Document Text

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...

## Related Documents

On the Left Notes
On the Right Notes
On the Right Notes
San Francisco Notes
On the Left Notes
On the Left Notes
On the Left Notes
On the Left Notes
On the Left Notes
On the Left Exam
On the Left Notes
Right Brain Notes
On the Right Notes
On the Right Notes
On the Right Exam
On the Right Notes