Leetcode: Search in Rotated Sorted Array. java

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

public class Solution {
	 public int search(int[] A, int target) {
		 int pivot = 0;
		 int n = A.length;
		 int left = 0, right = n - 1;
		 int mid = (left + right) / 2;
		 //find pivot
		 while (left <= right) {	
			 mid = (left + right) / 2;
			 if (A[left] >= A[mid])
				 right = mid - 1;
			 else 
				 left = mid + 1;
			 if (mid > 0 && A[mid] < A[mid - 1]) {
	         	pivot = mid;
	           	break;
			 }
	         if (mid < n - 1 && A[mid] > A[mid + 1]) {
	         	pivot = mid + 1;
	           	break;
	         }
	            	
		 }
		 left = 0;
		 right = n - 1;
		 //find target.
		 while (left <= right) {
			 mid = (left + right) / 2;
			 int m = (mid + pivot) % n;
			 if (target > A[m]) {
				 left = mid + 1;
			 }
			 else if (target < A[m]) {
				 right = mid - 1;
			 }
			 else
				 return m;
		 }
		 return -1;
	}
}