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

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

    while (head <= tail) {
      mid = (head + tail) / 2;
      if (target < A[mid]) {
        if (mid + 1 < A.length && A[mid + 1] < A[mid] && A[tail] >= target) {
          head = mid + 1;
        } else {
          tail = mid - 1;
        }
      } else if (target > A[mid]) {
        if (mid - 1 >= 0 && A[mid - 1] > A[mid] && A[head] <= target) {
          tail = mid - 1;
        } else {
          head = mid + 1;
        }
      } else {
        return mid;
      }
    }

    return -1;
  }