[leetcode]Search in Rotated Sorted Array II @ Python

原题地址:https://oj.leetcode.com/problems/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.

解题思路:还是二分查找的变种。需要考虑好边界情况。

代码:

[leetcode]Search in Rotated Sorted Array II @ Python
class Solution:
    # @param A a list of integers
    # @param target an integer
    # @return a boolean
    def search(self, A, target):
        left=0; right=len(A)-1
        while left<=right:
            mid=(left+right)/2
            if A[mid]==target: return True
            if A[left]==A[mid]==A[right]:
                left+=1; right-=1
            elif A[left]<=A[mid]:
                if A[left]<=target<A[mid]: right=mid-1
                else: left=mid+1
            else:
                if A[mid]<=target<A[left]: left=mid+1
                else:right=mid-1
        return False
[leetcode]Search in Rotated Sorted Array II @ Python

 

[leetcode]Search in Rotated Sorted Array II @ Python,布布扣,bubuko.com

[leetcode]Search in Rotated Sorted Array II @ Python

上一篇:Java里的生产者-消费者模型(Producer and Consumer Pattern in Java)


下一篇:java String 空指针异常