# 【LeetCode从零单刷】Search in Rotated Sorted Array I &amp;amp; II

I 题目：

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.

• [4,5,6,7,8,1,2]，中间值是 7，大于 tail=2。但是 head~mid 区间内必然是有序的，如果 [head] < target < [mid]，可以正常二分；如果不在，就继续对特殊区间 mid~tail 特殊二分处理
• [4,5,6,0,1,2,3]，中间值是 0，小于 head=4，但是 mid~tail 区间内必然是有序的，如果 [mid] < target < [tail]，可以正常二分；如果不在，就继续对特殊区间 head~mid 特殊二分处理

`class Solution {public: int search(vector<int>& nums, int target) { int size = nums.size(); int mid; int head = 0; int tail = size - 1; while (head <= tail) { if (nums[head] == target) return head; if (nums[tail] == target) return tail; mid = (head + tail) / 2; if (nums[mid] == target) return mid; if (nums[mid] < nums[head]) { if (nums[mid] < target && target < nums[tail]) head = mid + 1; else tail = mid - 1; } else if (nums[mid] > nums[tail]) { if (nums[head] < target && target < nums[mid]) tail = mid - 1; else head = mid + 1; } else { if (target < nums[mid]) tail = mid - 1; else head = mid + 1; } } return -1; }};`

II 题目：

What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

`class Solution {public: bool search(vector<int>& nums, int target) { int size = nums.size(); int mid; int head = 0; int tail = size - 1; while (head <= tail) { if (nums[head] == target) return true; if (nums[tail] == target) return true; mid = (head + tail) / 2; if (nums[mid] == target) return true; if (nums[mid] == nums[head]) { int i = head; for(; i <= mid; i++) { if (nums[i] != nums[mid]) { head = i; break; } } } if (nums[mid] == nums[tail]) { int i = tail; for(; i >= mid; i--) { if (nums[i] != nums[mid]) { tail = i; break; } } } if (nums[mid] < nums[head]) { if (nums[mid] < target && target < nums[tail]) head = mid + 1; else tail = mid - 1; } else if (nums[mid] > nums[tail]) { if (nums[head] < target && target < nums[mid]) tail = mid - 1; else head = mid + 1; } else { if (target < nums[mid]) tail = mid - 1; else head = mid + 1; } } return false; }};`

Top