Search in Rotated Sorted Array
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.
Analysis:
public class Solution { public int search(int[] A, int target) { int l = 0; int r = A.length - 1; while (l <= r) { int m = (l + r) / 2; if (A[m] == target) { return m; } if (A[m] >= A[l]) { if (A[l] <= target && target < A[m]) { r = m - 1; } else { l = m + 1; } } else { if (A[m] < target && target <= A[r]) { l = m + 1; } else { r = m - 1; } } } return -1; } }
Note:
sdfsdfweerwr
Search in Rotated Sorted Array II
Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.