http://www.geeksforgeeks.org/search-an-element-in-a-sorted-and-pivoted-array/

#include <iostream>
using namespace std;

#define CEIL(x, n) ((x) > (n) ? ((x) - (n)) : (x))

int binarySearchRotated(int *input, int n, int target) 
{
  if (n < 1)
    return -1;  
  
  int start = 0; 
  int end   = n - 1;
  for (int i = 0; i < (n - 1); i++) {
    if (input[i] > input[(i + 1)]) {
      start = i + 1;
      end   = i;
    }
  }

  if (end < start)
    end += n;
  
  int loop = 0;
  while(1) {
    loop++;
    if (start > end) {
      break;
    }
    int middle = start + ((end - start + 1) / 2);
    if (target == input[CEIL(middle, n)]) {
      cout << "loop = " << loop << "\n";
      return CEIL(middle, n);
    } else if (target > input[CEIL(middle, n)]) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }    
  }
  cout << "loop = " << loop << "\n";
  return -1;  
}

void swap(int *a, int *b)
{
  *a ^= *b;
  *b ^= *a;
  *a ^= *b;
}

int gcd(int a, int b) 
{
  int remain;
  if (a == 0 || b == 0)
    return (a < b ? b : a);
  
  while ((a > b ? (a %= b) : (b %= a))) {
  }
  return (a < b ? b : a);
}

void rotate(int *array, int n, int k)
{
  if (n < 2 || !array)
    return;
  
  if (k % n == 0) {
    return;
  } else {
    k = k % n;
  }
  
  int start, pos, temp;
  int cycle = gcd(n, k);
  for (int i = 0; i < cycle; i++) {
    pos = start = i;
    temp = array[start];
    while(1) {
      pos  = (pos + k) % n;
      if (pos == start) {
        array[pos] = temp;
        break;
      } else {
        swap(&temp, &(array[pos]));
      }
    }
  }
}

int binarySearch(int *input, int n, int target)
{
  int start  = 0;
  int end    = n - 1;
  
  if (n < 1)
    return -1;  
  
  int loop = 0;
  while(1) {
    loop++;
    if (start > end) {
      break;
    }
    int middle = start + ((end - start + 1) / 2);
    if (target == input[middle]) {
      cout << "loop = " << loop << "\n";
      return middle;
    } else if (target > input[middle]) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }    
  }
  cout << "loop = " << loop << "\n";
  return -1;
}

// To execute C++, please define "int main()"
int main() {
  int total  = 100;
  int *array = new int(total);
  for (int i = 0; i < total; i++) {
    array[i] = i;
  }
  
  rotate(array, total, 39);
  cout << "[ ";
  for (int i = 0; i < total - 1; i++) {
    cout << array[i] << ",";
  }
  cout << array[(total - 1)] << " ]\n";
  
  int r = binarySearchRotated(array, total, 77);
  cout << r << " " << array[r] << "\n";
  return 0;
}