No. 22 - Turning Number in an Array - solution

find_turning_number.cpp

//http://codercareer.blogspot.kr/2011/11/no-22-turning-number-in-array.html
//timecost : O(logN)

#include <assert.h>
#include <stdio.h>

int findTurningNumber(int * array, int length) {
  if (array == NULL || length <= 2)
    return -1;

  int left = 0;
  int right = length - 1;

  while (right > left + 1) {
    int middle = (left + right) / 2;
    if (middle == 0 || middle == length - 1)
      return -1;

    if (array[middle - 1] < array[middle] && array[middle] > array[middle + 1]) {
      printf("find turning number [%d] index [%d] \n", array[middle], middle);
      return middle;
    }  else if (array[middle - 1] < array[middle] && array[middle] < array[middle + 1]) {
      left = middle;
    }  else {
      right = middle;
    }
  }

  return -1;
}

int main(void) {
  printf("start test \n");

  int array1[10] = {1,2,3,4,5,6,5,3,2,1};
  int array2[10] = {2,4,6,8,10,12,14,16,10,6};
  int array3[10] = {3,5,9,14,9,6,5,3,2,1};
  int array4[10] = {5,10,15,10,9,8,4,3,2,1};
  int array5[10] = {1,15,10,9,8,5,4,3,2,1};

  assert(findTurningNumber(array1, 10) == 5);
  assert(findTurningNumber(array2, 10) == 7);
  assert(findTurningNumber(array3, 10) == 3);
  assert(findTurningNumber(array4, 10) == 2);
  assert(findTurningNumber(array5, 10) == 1);

  return 1;
}