Description

Programming assignment 2.

In this assignment, we will apply the idea of binary search to solve the below questions.

Note: The running time of your solutions should be O(logn).

Question 1. Implementing the square root function: Write a function that asks a user to enter an integer N

and returns ⌈√𝑁⌉.

Example 1: input: 28

Output: 6

Example 2: input: 16

Output: 4

(Note:

• You are NOT allowed to use the built-in sqrt function in your code • Do NOT use any type of array in your code)

Question 2. Given a sorted array of n distinct numbers where the range of the numbers are between 0 to m and m > n (m is given by user). Find the smallest missing number.

Example 1: input: a = [0, 1, 3, 6, 8, 9], m = 10

Output: 2

Example 2: input: a = [2, 5, 7, 11], m = 15

Output: 0

Example 3: input: a = [0, 1, 2, 3, 4], m = 8

Output: 5

Example 4: input: a = [12], m = 13

Output: 0