LeetCode-二分搜索

LeetCode33 搜索旋转排序数组(无重复数字)

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        n = len(nums)
        l,r = 0,n-1
        while l<=r:
            m = (l+r)>>1
            if nums[m] == target:
                return m
            if nums[l] <= nums[m]:
                if nums[l]<=target<nums[m]:
                    r = m-1
                else:
                    l = m+1
            else:
                if nums[m]<target<=nums[r]:
                    l = m+1
                else:
                    r = m-1
        return -1

LeetCode81. 搜索旋转排序数组 II（有重复数字）

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        l,r = 0,len(nums)-1
        while l<=r:
            m = (l+r)>>1
            if nums[m] == target:
                return True
            if nums[m] > nums[l]:
                if nums[l] <= target <nums[m]:
                    r = m-1
                else:
                    l = m+1
            elif nums[m] < nums[l]:
                if nums[m] < target <=nums[r]:
                    l = m+1
                else:
                    r = m-1
            else:
                l = l+1
        return False

LeetCode162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

---

分析：
如果nums[mid] > nums[mid+1]，则在mid之前一定存在峰值元素
如果nums[mid] < nums[mid+1]，则在mid+1之后一定存在峰值元素

---

class Solution(object):
    def findPeakElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l,r = 0,len(nums)-1
        while l<r:
            mid = (l+r)>>1
            if nums[mid]<nums[mid+1]:
                l = mid+1
            else:
                r = mid
        return l

LeetCode852. 山脉数组的峰顶索引

我们把符合下列属性的数组 A 称作山脉：

• A.length >= 3
• 存在 0 < i < A.length - 1 使得A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1]
  给定一个确定为山脉的数组，返回任何满足 A[0] < A[1] < … A[i-1] < A[i] > A[i+1] > … > A[A.length - 1] 的 i 的值。

class Solution(object):
    def peakIndexInMountainArray(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        l,r = 0,len(A)
        while l<r:
            mid = (l+r)>>1
            if A[mid]>A[mid+1]:
                r = mid
            else:
                l = mid+1
        return l