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.
Solution:
public class Solution { public int search(int[] A, int target) { int begin = 0; int end = A.length-1; boolean targetInRotated = target>=A[0]; while(begin<=end) { int midpoint = (begin+end)/2; if(A[midpoint]==target) return midpoint; else if(targetInRotated && A[midpoint]<A[0]) end = midpoint - 1; else if(!targetInRotated && A[midpoint]>=A[0]) begin = midpoint + 1; else if(A[midpoint]<target) begin = midpoint + 1; else end = midpoint -1; } return -1; } }
No comments :
Post a Comment