Leetcode33. Search in Rotated Sorted Array

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

Suppose an array sorted in ascending order 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.

我的代码：时间复杂度O(n)

下标版本：

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-33
//T(n)=O(n), S(n)=O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {
        decltype(nums.size()) index = 0;
        for(; index < nums.size(); ++index)
        {
            if(nums[index] == target)
            {
                return index;
                break;
            }
        }
        return -1;
    }
};

迭代器版本：

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-33
//T(n)=O(n), S(n)=O(1)
class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(auto vbeg = nums.begin(); vbeg != nums.end(); ++vbeg)
        {
            if(*vbeg == target)
            {
                return distance(nums.begin(), vbeg);
                break;
            }
        }
        return -1;
    }
};

优秀代码：时间复杂度O(logn)

实际上，这个array是有序的，只是有一个旋转，所以，可以采用适当的算法来优化时间复杂度。

//二分查找
class Solution {
public:
int search(const vector<int> &nums, int target)
{
    int lo = 0;
    int hi = nums.size() - 1;
    while (lo <= hi)
        {
            int mid = (lo + hi) / 2;
            if (nums[mid] == target) return mid;
            if (nums[lo] <= nums[mid]) //lo与mid之间有序
                {
                    if (target >= nums[lo] && target < nums[mid])
                        {
                            hi = mid - 1;
                        }
                    else
                        {
                            lo = mid + 1;
                        }
                }
            else//lo与mid之间无序，那么mid和hi之间一定有序
                {
                    if (target > nums[mid] && target <= nums[hi])
                        {
                            lo = mid + 1;
                        }
                    else
                        {
                            hi = mid - 1;
                        }
                }
        }
    return -1;
}
};

• 怎样理解lo与mid之间无序，那么mid和hi之间一定有序？
• • 把题目的要求理解为只有一个轴发生了旋转，那么一旦nums[lo]<=nums[mid]不成立，那么mid和hi之间的元素一定是有序的！
• • 
• 对二分查找的几个key：
• • 外层循环使用low<=high
• • 内层控制low = mid + 1 或者 high = mid - 1
• • mid = (lo + hi)/2
• • 找到的值一定是通过mid返回，一旦lo == hi时仍然没有nums[mid] == target，则查找失败;下次循环之后，lo > hi，循环结束。
• • 判断lo和mid时间是否有序，一定要使用nums[lo] <= nums[mid]，如下图：
• • 
• • 上面的案例给我的启发：在判断区间有序时，一定要把=加上nums[lo] <= nums[mid]，如果不加，会造成上述问题，即，认为mid和hi之间[3,1]有序，在判断target > nums[mid] && target <= nums[hi]时，就会排除区间[3,1]，但是，实际上，要找的1就在该区间内。

改进一些语言特性：符合$C++ 11$标准