Koofers

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 Search
  • On the Right
  • On the Left
  • Immediately
  • Root Element
  • Original Problem
  • In Front Of
  • In Front (of)
  • Linked List
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

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
155, "/var/app/current/tmp/"