Binary Search Shortlist

Cosmin Negruseri
16 mai 2014

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⁰ > A¹ 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.