地址：https://oj.leetcode.com/problems/search-in-rotated-sorted-array/

非递归进行剪枝搜索版本：

public class Solution {	public int search(int[] A, int target) {		int low =0, high = A.length-1;			// high 小于target 从low开始搜索			if(A[high]<target){				int pivot = A[high];				while(low<=high ){					// 如果low大于target 或者low小于pivot 直接返回没找到					if(A[low]>target || A[low]<pivot){						return -1;					}else {						if(A[low]==target)							return low;					}					low++;				}			}else {				int pivot = A[high];				while(low<=high){					if(A[high]<target || A[high]>pivot){						return -1;					}					if(A[high]==target)						return high;					high--;				}			}		return -1;	}}

递归版本实现：

public class Solution {       public static int search(int[] A, int target) {          return rec(A, target, 0, A.length-1);      }             // 递归查找      public static int rec(int[] A, int target, int low, int high){          if(low > high){              // 没找到的情况              return -1;          }                     int mid = low + (high-low)/2;          if(A[mid] == target){       // 找到了              return mid;          }                     int res = rec(A, target, low, mid-1);       // 在左侧查找          if(res == -1){          // 如果左侧没找到，继续在右侧查找              res = rec(A, target, mid+1, high);          }                     return res;      }  }

Search in Rotated Sorted Array