Thursday, October 18, 2012

Unimodal array has an increasing sequence followed by decreasing sequence, find the number at which the transition happens

  Unimodal array contains a list of 'N' integers. There exists M < N, such that
  a[0] to a[M] are in increasing series
  a[M+1] to a[N] are in decreasing series
  The problem is to find a[M] in O(Log N)
  E.g. {2, 4, 8, 10, 13, 18, 12, 7, 5, 4}. Here M is 18 as the switch happens after it


No comments:

Post a Comment