def f1(n):
	l = []
	for i in range(n):
		l.insert(0,i)
	return

def test_binarySearchNormal():
	assert binarySearch([1,2,3,4,5,6,7,8,9,10], 5) == True
	assert binarySearch([1,2,3,4,5,6,7,8,9,10], -1) == False
	assert binarySearch([1,2,3,4,5,6,7,8,9,10], 11) == False
	assert binarySearch([1,2,3,4,5,6,7,8,9,10], 1) == True
	assert binarySearch([1,2,3,4,5,6,7,8,9,10], 10) == True

def test_binarSearchDuplicates():
	assert binarySearch([-10,-5,0,1,1,4,4,7,8], 0) == True
	assert binarySearch([-10,-5,0,1,1,4,4,7,8], 2) == False
	assert binarySearch([-10,-5,0,1,1,4,4,7,8], 4) == True
	assert binarySearch([-10,-5,0,1,1,4,4,7,8], 2) == False

def test_binarySearchEmptyList():
	assert binarySearch([], 0) == False

def test_binarySearchSameValues():
	assert binarySearch([5,5,5,5,5,5,5,5,5,5,5], 5) == True
	assert binarySearch([5,5,5,5,5,5,5,5,5,5,5], 0) == False

def binarySearch(intList, item):
	first = 0
	last = len(intList) - 1
	found = False

	while first <= last and not found:
		mid = (first + last) // 2
		if intList[mid] == item:
			found = True
		else:
			if item < intList[mid]:
				last = mid - 1
			else:
				first = mid + 1
	return found

def binarySearch(intList, item):
	if len(intList) == 0: # base case
		return False

	mid = len(intList) // 2
	if intList[mid] == item:
		return True
	elif item < intList[mid]:
		return binarySearch(intList[0:mid], item)
	else:
		return binarySearch(intList[mid+1:], item)

Time:
* In-person (BRDA 1610), Thursday 2/6 11am - 12:15pm PST

Logistics:
* Bring a writing utensil and student ID
* Please write legibly (if we can't read your answer, we can't grade it)
* When leaving the room, you must hand in your exam and present your ID
* Closed book (no notes / book / electronic devices)
* TAs and I will be proctoring the exam. We can answer any CLARIFYING questions

Possible Types of Questions:
* True / False (if False, briefly state why (1 sentence))
* Short Answer - Briefly define / state / describe / ...
* Given some code, write the output / state the O-notation
* Write code satisfying a specification
* Given some partial algorithm, fill in the blank to make it work
* Draw diagrams

Midterm Topics:

Will cover material from the beginning of the class up until the end of week 4's (1/30) lecture

Python Basics 
- Types
    * I don't expect students to know ALL Python basics, but do expect students to know
    the ones we explicitly covered in lectures and/or assignments
    * int, float, boolean, strings, lists, sets, dictionaries, ...
    * conversion functions (int(), float(), str(), ...)
    * mutable vs. immutable
- Relational / logical operators (==, <, >, <=, >=, and, or, not, ...)
- Python Lists
    * Supporting methods (count, pop, append, insert, ...)
    * List / string slicing [:]
- Understanding under-the-hood functionality of lists and dictionaries
- Strings
    * Supporting methods (replace, split, find, ...)
- Function definitions
- Control Structures (if, else, elif, for, while, ...)

Python Errors / Exceptions
- Runtime vs. Syntax errors
- Exception types (NameError, TypeError, ZeroDivisionError, ...)
- Exception handling
    * try / except / raise
    * Flow of execution
    * Passing exceptions to function / method caller(s) when not handled in try / except
    * Multiple except blocks
    * Handling Exceptions in an Inheritance hierarchy

Object Oriented Programming
- Defining classes and methods
- constructors (defining / initializing default state)
- Shallow vs. Deep equality (overloading __eq__ method)
- Overloading operators (__str__, __add__, __le__, ...)
- Inheritance
    * know method lookup for inheritance hierarchy
    * implementation for inherited fields / methods
    * overriding inherited methods
    * calling super / base class(es) methods

Testing
- Test Driven Development (TDD)
- pytest

Algorithm Analysis and O-notation
- Know how to derive O-notation for snippets of code

Recursion
- Implementation of recursive functions and O-notation analysis
- Understanding how recursive algorithms are managed by the call stack
- Draw call stack given a recursive function

Binary Search
- Search for items in a SORTED list
- Know the implementations (as covered in textbook / lecture) and O-notation