假设有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。 你可以假设数组中不存在重复的元素。
直接的方法是顺序搜索 更好的方法是二分搜索
public class Solution { /** *@param A : an integer rotated sorted array *@param target : an integer to be searched *return : an integer */ public int search(int[] A, int target) { // write your code here // write your code here //二分搜索 if (A == null || 0 == A.length) return -1; int left = 0; int right = A.length - 1; int mid = -1; while (left < right - 1) { mid = (left + right) / 2; if (target == A[mid]) { return mid; } if (A[left] < A[mid]) { if (A[left] <= target && A[mid] >= target) { right = mid; } else { left = mid; } } else { if (A[mid] <= target && A[right] >= target ) { left = mid; } else { right = mid; } } } if (target == A[left]) { return left; } else if (target == A[right]) { return right; } else { return -1; } //直接搜索 // if(A.length < 1) // return -1; // if(A[0] > target){ // for(int i = 1;i < A.length;i++){ // if(target == A[A.length-i]) // return A.length - i; // else if(target > A[0]) // return -1; // } // } // else if(A[0] < target){ // for(int i = 1;i < A.length;i++){ // if(target == A[i]) // return i; // else if(target < A[0]) // return -1; // } // } // else // return 0; // return -1; }}新闻热点
疑难解答
