DB2 - WS 2015/16 - Assignment 3 (Binary Search)
===============================================

1) Download.

   Download the file 'assignment3.zip' and unpack it.

   Rename nnnnnnn_3.py to matrikel_3.py, such that if your matrikel number is 
   1234567 the file is named 1234567_3.py

   ATTENTION: Please stick to the naming convention because your assignments 
   are fetched, processed, and verified automatically. If the file name is 
   incorrect we may miss your assignment.

2) Assignment description.

   In this assignment we imitate the binary search on tuples stored in blocks. 
   The tuples are sorted integer numbers stored in an array of blocks (our class
   'Blocks'). Each block (our class 'Block') has a fixed capacity of at most 
   64 tuples. Each time the program is executed, the tuples are randomly 
   generated with the following assumptions:
   - We fix three tuple values and their occurrences: value '31' occurs 7 times,
     value '67' occurs 70 times, value '102' occurs 270 times.
   - Before and after tuples with the fixed values we generate 1000000 tuples 
     with random values resulting in the following sorted sequence of tuples: 
     A,31,...,31,B,67,...,67,C,102,...,102,D where A, B, C, and D are 1000000 
     sorted tuples.
   - The generated tuples are split into blocks while initializing an object 
     of class 'Blocks' (see the constructor method '__init__' of class 'Blocks').

   The generation of the tuples is done by 'tuples.py' module. Please do not 
   modify the content of 'tuples.py' file.

   'tuples.py' contains only an example configuration for generating our
   sequence of tuples. While evaluating your solutions, we may change this 
   configuration to verify more test cases.

   The input to our program is the name of the search method ('scan' or 
   'binsearch') and the value to be found in the sequence of tuples described 
   above.

   The output is the number of occurrences of the searched value and the number 
   of block accesses required to perform the search. Depending on the 
   implementation details, the exact number of block accesses may differ. We 
   will consider that fact when evaluating your solutions.

   As an example, we implemented 'scan' method which reads all the blocks one 
   by one.

   You may execute the code by calling

   python nnnnnnn_3.py {scan|binsearch} N

   where N is the value to search for.

   If you do not have python installed on your machine, the machines in the
   computer lab room and the sshstud machine have it installed. 

3) Task: Implement binary search on blocks.

   Your task is to implement the 'binsearch' method which performs a binary 
   search on the blocks. Some hints to consider while implementing:
   - The first step is to find a block containing tuples with the searched 
     value. This step should be done with binary search.
   - The tuples with the searched value can span over multiple blocks, for 
     example, the value '67' comes 70 times which means that tuples holding this
     value can be stored in up to three blocks.
   - Once you find the first block containing the searched value, you have to 
     ensure that you verify the blocks before and after, but only if necessary.

   IMPORTANT: Please do not change the output format of the program.

4) Submission.

   Submit your solution by sending an email to dbabgabe@cosy.sbg.ac.at 
   with a title DB2:matrikel_3 (for example, if you matrikel number is 1234567
   the title should be: DB2:1234567_3) and an attachment matrikel_3.py

   IMPORTANT: Please do not submit the file 'tuples.py'.

   ATTENTION: The filename and the email title are important. You may fail if 
   you do not stick to the format.