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
  • Root Element
  • Immediately
  • Original Problem
  • Binary Search Tree
  • Computer Science Ii
  • Linked List
  • In Front Of
Login / Sign Up to View Document
Preview Page 1Preview Page 2Preview Page 3Preview Page 4Preview Page 5Preview Page 6

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