Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2014-05-16 06:23:11.
Revizia anterioară   Revizia următoare  

Binary Search Shortlist

Cosmin
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 the value x occur in A.
  2. Given a real number x, find out it’s cubic root.
  3. Given A a sorted array, find out an i such that A[i] == i.
  4. Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log2x.
  5. Given an array A such that A0 > A1 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.
Categorii: