Answer all questions c++

I. Write a C++ Program to implement Binary Search algorithm? (10 Points) II. Write a C++ Program to implement Interpolation Search Algorithm? (10 Points) III. Write a C+ Program to Implement Hash Tables with Linear Probing? (10 Points) IIII. Write the algorithm steps to implement interpolation search? (5 Points) V. Given an array arrof n elements, write a function to search a given element x in arr . (5 Points) Example: Input: arr[ ] = { 10, 20, 80, 30, 60, 50, 110, 100, 130, 170; x-110 Output: 6 Element x is present at index 6 VI. Choose th (10 Points). 2 points nswe 1) Which of the following is correct recurrence for worst case of Binary Search? a) T(n) = 2T(n/2) + 0( 1 ) and T(1) = T(0) = O( 1 ) b) T(n) = T(n-l ) + 0(1) and T( 1 )-T(0) = 0(1) c) T(n) = T(n/2) + 0(1) and T(1) = T(0)-0(1) d) T(n) = T(n-2) + O( 1 ) and T( 1 ) = T(0)-0(1)