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
