Leetcode 81 Search in Rotated Sorted Array II

triplebee

发布于 2018-01-12 14:56:21

5810

发布于 2018-01-12 14:56:21

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

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.

在循环错位的有序数组中进行搜索，与33题类似

https://cloud.tencent.com/developer/article/1019304

不同的是元素可能重复，

当遇到等于的时候，只能一个个地缩小区间，而不能以log复杂度减小，所以在最坏情况下，效率会退化为O(n).

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l=0,r=nums.size()-1;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            if(nums[mid]==target) return true;
            if(nums[mid]<nums[l])
            {
                if(target<nums[l] && target>nums[mid])
                    l=mid+1;
                else
                    r=mid-1;
                    
            }
            else if(nums[mid]>nums[l])
            {
                if(target>=nums[l] && target<nums[mid])
                    r=mid-1;
                else
                    l=mid+1;
            }
            else
                l++;  //mid和l值相等，无法获知mid的位置
        }
        return false;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2016-09-23 ，如有侵权请联系 cloudcommunity@tencent.com 删除

duplicates