## Wednesday, November 12, 2014

### [LeetCode] Search in Rotated Sorted Array I, II

Search in Rotated Sorted Array 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.

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.

A[mid] < target <= A[end], 右半序列，否则为左半序列。

A[start] <= target < A[mid], 左半序列，否则为右半序列

Base case：当start + 1 = end时

A[mid] = A[start] = 2 < A[end]，A[mid] < target <= A[end] 右半序列，否则左半序列

A[mid] = A[start ] = 4 > A[end],  A[start] <= target < A[mid] 左半序列，否则右半序列

A[mid] =  target, 返回mid，否则

(1) A[mid] < A[end]: A[mid+1 : end] sorted
A[mid] < target <= A[end]  右半，否则左半。

(2) A[mid] > A[end] : A[start : mid-1] sorted
A[start] <= target < A[mid] 左半，否则右半。

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25``` ```class Solution { public: int search(int A[], int n, int target) { return searchRotatedSortedArray(A, 0, n-1, target); } int searchRotatedSortedArray(int A[], int start, int end, int target) { if(start>end) return -1; int mid = start + (end-start)/2; if(A[mid]==target) return mid; if(A[mid]A[mid] && target<=A[end]) return searchRotatedSortedArray(A, mid+1, end, target); else return searchRotatedSortedArray(A, start, mid-1, target); } else { // left half sorted if(target>=A[start] && target

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24``` ```class Solution { public: int search(int A[], int n, int target) { int start = 0, end = n-1; while(start<=end) { int mid = start + (end-start)/2; if(A[mid]==target) return mid; if(A[mid]A[mid] && target<=A[end]) start = mid+1; else end = mid-1; } else { // left half sorted if(target>=A[start] && target

3 1 2 3 3 3 3
3 3 3 3 1 2 3

A[mid] = A[end] != target时：搜寻A[start : end-1]

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```class Solution { public: bool search(int A[], int n, int target) { int start = 0, end = n-1; while(start<=end) { int mid = start + (end-start)/2; if(A[mid]==target) return true; if(A[mid]A[mid] && target<=A[end]) start = mid+1; else end = mid-1; } else if(A[mid]>A[end]) { // left half sorted if(target>=A[start] && target