假設(shè)有一個(gè)排序的按未知的旋轉(zhuǎn)軸旋轉(zhuǎn)的數(shù)組(比如，0 1 2 4 5 6 7 可能成為4 5 6 7 0 1 2)。給定一個(gè)目標(biāo)值進(jìn)行搜索，如果在數(shù)組中找到目標(biāo)值返回?cái)?shù)組中的索引位置，否則返回-1。 你可以假設(shè)數(shù)組中不存在重復(fù)的元素。
直接的方法是順序搜索 更好的方法是二分搜索
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; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
