Figure out an algorithm for each of the following problems. What’s the complexity? Code it.

* Given A, a sorted int array of length n. How many times the value x occur in A.
* Given a real number x, find out it’s cubic root.
* Given A a sorted array, find out an i such that A[i] == i.
* Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log2x.
* Given an array A such that A[0] > A[1] and A[n-1] > A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).
* Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
* Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.
* Given two sorted arrays of length n and m, find out the kth element of their sorted union.
* An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array.
* Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.

# Given A, a sorted int array of length n. How many times does the value x occur in A.
# Given a real number x, find out it’s cubic root.
# Given A a sorted array of distinct integers, find out an i such that A[i] == i.
# Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log_2(x).
# Given an array A such that A[ 0] > A[ 1] and A[n-1] > A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).
# Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
# Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.
# Given two sorted arrays of length n and m, find out the kth element of their sorted union.
# An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct int values, determines whether a given integer is in the array.
# Write a program that, given an array of N distinct int values in ascending order, determines whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory. The running time of your program should be proportional to log N in the worst case.

private

protected

9865