Answers file: Binary search
===========================

Replace the placeholders "..." with your answers.


Your very first task
--------------------

1. What is your name? John Croft

2. What is your favourite colour? Blue


Part 3. Test your implementation
--------------------------------

Note: answer this question by running your code and counting the comparisons.
See the README for some hints on how to do this.

3. How many comparisons does first_index_of use at most for an array of:

a) 10 elements? 5
b) 100 elements? 8
c) 1,000 elements? 11
d) 1,000,000 elements? 21

The worst case should be a value at the lower bound, ie. f(array[range(n)], 0)



Part 4. Reason about your implementation
----------------------------------------

4. How many comparisons would first_index_of need for 1,000,000,000,000 elements?
   (This is way too big for your computer's memory!)
   Justify your answer.

first_index_of has a complexity of log2(n) and always checks the input exhaustively, and has a final comparison. 
It therefore needs log2(1,000,000,000,000) + 1 = 41 comparisons.


Appendix: general information
-----------------------------

A1. How many hours did you spend on the assignment?

8-9 hrs


A2. Do you know of any bugs or limitations?

Perhaps there is a way to eliminate the final comparison first_index_of, but I can't think of it.


A3. Did you collaborate with any other students on this lab?
    If so, write with whom and in what way you collaborated.
    Also list any resources (including the web) you have used in creating your design.

No collaboration.
I used the coursebook, and various python tutorial sites for python syntax help.


A4. Did you encounter any serious problems?

No.


A5. Do you have other comments or feedback?

No.