# 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 LeftImmediatelyRoot ElementOriginal ProblemIn Front OfIn Front (of)Linked List

## Sample Document Text

CS112-2008S-33 Binary Search & Trees 1 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, continue looking 33-5: Binary Search CS112-2008S-33 Binary Search & Tree...

## 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
San Francisco 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 Notes