# Leetcode: Search in Rotated Sorted Array & Search in Rotated Sorted Array II

## 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.

Reference

Share