Binary Search Shortlist

Cosmin Negruseri
16 mai 2014

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

1. Given A, a sorted int array of length n. How many times does the value x occur in A.
2. Given a real number x, find out it’s cubic root.
3. Given A a sorted array of distinct integers, find out an i such that A[i] == i.
4. Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log_2(x).
5. 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]).
6. Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.
7. 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.
8. Given two sorted arrays of length n and m, find out the kth element of their sorted union.
9. 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.
10. 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.