Thursday, December 19, 2013


Interview question : Find min in shifted array : {26, 33, 49, 63, 3, 7, 13, 18, 19, 23)

int Min(int[] numbers)
{
if ( numbers == null || numbers.Length <= 0) throw new Exception();
int min = numbers[0];
for (int i = 1; i < numbers.Length; i++)
{
if (numbers[i] < min )
{
  min = numbers [i];
  break; // for shifted - sorted array
}
}
return min;
}

// binary chop
int Min (int[] numbers, int start, int end)
{
// validate parameters
// termination condition
if (start == end]) return numbers[start];
if (numbers[start] > numbers[end])
{
  int mid = start + end / 2;
  if ( numbers[start] > numbers[mid])
  return Min(numbers, start, mid);
  else
  return Min(numbers, mid+1, end);
}
else
return numbers[start];
}




No comments:

Post a Comment