Python Binary Search ( Compare to 154)
The problem 154 is harder than 153. \n\nAt first , we need to solve 153 ( no duplicate exists in the array )\n\n153.Find Minimum in Rotated Sorted Array:\n\nThe
The problem 154 is harder than 153. \n\nAt first , we need to solve 153 ( no duplicate exists in the array )\n\n153.Find Minimum in Rotated Sorted Array:\n\nThese problems give no clear target , we can use ```nums[r]``` as judgement condition  \nIt is very easy to find\uFF1A\n>if nums[mid] > nums[r]: # [3,4,5,1,2]\n>l = mid+1 # min exist on the right side of the middle value\n\n>if nums[mid] < nums[r]: # [1,2,3,4,5] ,[4,5,1,2,3]\n>r = mid # min exist on the left side of the middle value ( inclue middle value)\n\n>if nums[mid] == nums[r]: # Invalid\n\nCombining these conditions\uFF1A\n```python\n# 153. Find Minimum in Rotated Sorted Array\ndef findMin(self, nums: List[int]) -> int:\n    l, r = 0, len(nums)-1\n    while l < r:\n        mid = (l+r)//2\n        if nums[mid] > nums[r]:\n            l = mid+1\n        else:\n            r = mid\n    return nums[l]\n```\n\n---------------------------------------\n\n154.Find Minimum in Rotated Sorted Array II:\n\nSame idea with 153\n\nIt is very easy to find\uFF1A\n>if nums[mid] > nums[r]: # [3,4,5,1,2]\n>l = mid+1 # min exists on the right side of the middle value\n\n>if nums[mid] < nums[r]: # [1,2,3,4,5] ,[4,5,1,2,3]\n>r = mid # min exists on the left side of the middle value ( inclue middle value)\n\nHere are the different parts\uFF1A\n\n```python\nif nums[mid] == nums[r]: # valid\n\tif nums[mid] == nums[l]: # [10, 5, 10, 10, 10] or [10, 10, 10, 5, 10] \n\t\tl = l+1 # or r = r-1 # min could be on either side\uFF0Cwe just narrow the interval\n\telif nums[l] < nums[mid]:  # [1, 5, 10, 10, 10]  \n\t\tr = mid-1\n\telse:# [20, 5, 10, 10, 10]  or [20, 10, 10, 10, 10]\n\t\tr = mid\n```\n\nCombining these conditions\uFF1A\n```python\n\t# 154. Find Minimum in Rotated Sorted Array II\n    def findMin(self, nums: List[int]) -> int:\n        l, r = 0, len(nums)-1\n        while l < r:\n            mid = (l+r)//2\n\t\t\t# condition for 154\n            if nums[mid] == nums[r]:\n                if nums[mid] == nums[l]:\n                    l = l+1 # or r = r-1\n                elif nums[l] < nums[mid] :  \n\t                r = mid-1\n                else:\n                    r = mid\n\t\t\t# same as 153\n            elif nums[mid] > nums[r]:\n                l = mid+1\n            else:\n                r = mid\n        return nums[l]\n```\n\nWe can combine the judgment conditions in the loop, and choose a larger interval when we combine\n\n```python\n\t# 154. Find Minimum in Rotated Sorted Array II\n    def findMin(self, nums: List[int]) -> int:\n        l, r = 0, len(nums)-1\n        while l < r:\n            mid = (l+r)//2\n            if nums[mid] == nums[r]:\n                if nums[mid] == nums[l]:\n                    l = l+1 # or r = r-1\n                else:\n                    r = mid\n            elif nums[mid] > nums[r]:\n                l = mid+1\n            else:\n                r = mid\n        return nums[l]\n```
['Binary Search', 'Python3']