public int search(int[] A, int target) {

    int head = 0;
    int tail = A.length - 1;
    int mid = 0;

    while (head <= tail) {
      mid = head + (tail - head) / 2;
      if (A[mid] == target) {
        return mid;
      }

      if (A[head] <= A[mid]) {
        if (target >= A[head] && target <= A[mid]) {
          tail = mid - 1;
        } else {
          head = mid + 1;
        }
      } else {
        if (target >= A[mid] && target <= A[tail]) {
          head = mid + 1;
        } else {
          tail = mid - 1;
        }
      }
    }

    return -1;
  }