leetcode81-- Search in Roted Sorted Array 2

leetcode81-- Search in Roted Sorted Array 2

题目

题目和之前的leetcode33基本一样,但是这次里面的元素可能会有重复的,那么不同在于现在有一种情况是不能免确定哪边重了,即不好判断哪半边是有序的了,

其实只需要在刚才的基础上把“start”再加一位就可以了。

如下

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        if len(nums)==0:
            return False
        
        start, end = 0, len(nums)-1
        
        while(start+1<end):
            mid = start+(end-start)/2
            
            if nums[mid] == target:
                return True
            
            elif nums[start]<nums[mid]:
                if nums[start]<=target and target<=nums[mid]:
                    end = mid
                else:
                    start = mid
                    
            elif nums[start]>nums[mid]:
                if nums[mid]<=target and target<=nums[end]:
                    start = mid
                else:
                    end = mid
                
            else:
                start += 1
        
        
        if nums[start] == target or nums[end]==target:
            return True
        
        return False
    

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦