Python binary search.

The goal of this assignment will be to practice in this using binary search, a notoriously bug-prone algorithm.

You will be given three implementations of binary search that are expected to satisfy the following specification:

Input: array arr of integers sorted in a nondecreasing order and an integer k;

Output: an index i such that arr[i] = k and None if such index does not exist;

Complexity: the complexity of the algorithm must be O(logn) where n is the length of arr.

Each of the implementations does not quite satisfy the specification. For each of the implementations, you will be asked to do three things:

1. Point out the bug, that is which part of the specification above is violated. If there is a problem with input-output behaviour, a sample input must be provided. If you think that something is wrong with the complexity, an argument must be given.

2. Suggest a fix of the bug. Important thing is that you are not asked to provide any correct implementation of binary search. Your task is actually to fix this one, so the most of the code should remain unchanged.

3. Suggest a natural test that could help to avoid the bug. "Natural" is an important word here. For example, it is not enought to exhibit an input that would produce an incorrect output. You should also explain that this is a natural input to test without knowing about this bug or find a more natural input.

First task:

Second task:

Third task: