public int BS (int[] A, int key, int first, int last) {
  while(first!=last) {
    int mid=(first+last)/2;
    if(key==A[mid])
    return mid;
    if(A[first]<=A[mid]) { //no matter hoe to rotated it,there always exits a half of sorted array. And we will classify according to this.
      if(key>A[first]&&key<A[mid])
      last=mid;
      else
      first=mid+1;
    }
    else {
      if(key>A[mid]&&key<A[last-1])
      first=mid+1;
      else
      last=mid;
    }
  }
  return -1;
}