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.

个人思路：

1，这个题只需要考虑从小到大的排序情况，不用考虑从大到小的情况

2，通过几个例子来找出规律，比如数组012345678，经过旋转有如下3种情况：

　　1，345678012，mid=7，mid左边是有序的，右边还是一个旋转数组

　　2，780123456，mid=2，mid右边是有序的，左边还是一个旋转数组

　　3，012345678，mid=4，两边都是有序的情况

现在来找出beign（起始值），mid（中间值），end（末尾值）三者之间的关系

　　1，当mid>begin，有可能是1和3这两种情况，那么左边是有序的，可以用target与begin和mid值比较，若在begin和mid范围，则就在该段范围内查找即可，不用再管右边的元素了，若不在begin和mid范围内，则说明target在mid和end之间，将begin设置为mid+1，然后用同样的方式在新的begin和end之间查找即可

　　2，当mid<begin，则是2这种情况，那么右边是有序的，则用target与mid和end值比较，若在mid和end范围，则就在该段范围内查找即可，不用再管左边的元素了，若不在mid和end范围内，则说明target在begin和end之间，将end设置为mid-1，然后用同样的方式在新的begin和end之间查找即可

　　3，当mid==begin，若仅仅是为了解第1题，则可将该种情况的判断合并到1里即可，但如果是第2题，由于有重复元素，需要单独判断，比如数组13111和11131都是mid==begin，但是一个是3在左边，一个是3在右边，就不能依据mid和begin的比较情况来缩小一半的范围，需要将begin++，一步一步往下看

　　4，若mid的值刚好为target，则返回即可

3，这里说下第1题里面两个特殊的测试用例，一个是数组元素只有2个的时候，另外一个是数组元素只有1个的时候，当出现这两种情况的时候，mid等于begin

4，做这题的时候，主要是要找到规律以便使用二分查找，还有就是考虑几个特殊的情况

代码：（将返回值改一下也可以AC第2题）

 1 class Solution { 2 public: 3     int search(int A[], int n, int target) { 4         int begin = 0, end = n - 1; 5         int mid; 6         while (begin <= end) 7         { 8             mid = (begin + end) / 2; 9             if (A[mid] == target)10             {11                 return mid;12             }13             if (A[mid] > A[begin])14             {15                 if (target >= A[begin] && target < A[mid])16                 {17                     end = mid - 1;18                 }19                 else20                 {21                     begin = mid + 1;22                 }23             }24             else if (A[mid] < A[begin])25             {26                 if (target > A[mid] && target <= A[end])27                 {28                     begin = mid + 1;29                 }30                 else31                 {32                     end = mid - 1;33                 }34             }35             else36             {37                 ++begin;38             }39         }40         return -1;41     }42 };

View Code

leetcode - Search in Rotated Sorted Array I & II