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, 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, 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 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.

public

protected