二分查找的四种变形 by Python

四种常见二分查找变形问题：

• 注：假定测试数据都是从小到大的有序数组
• 查找第一个等于给定值的元素

class Solution:
    def bsearch(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        low, high = 0 ,len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] == val:
                if mid == 0 or nums[mid-1] != val:
                    return mid
                else:
                    high = mid - 1
            elif nums[mid] > val:
                high = mid - 1
            else:
                low = mid + 1
        return -1

• 查找最后一个等于给定值的元素

class Solution:
    def bsearch(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        low, high = 0 ,len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] == val:
                if mid == len(nums)-1 or nums[mid+1] != val:
                    return mid
                else:
                    low = mid + 1
            elif nums[mid] > val:
                high = mid - 1
            else:
                low = mid + 1
        return -1

• 查找第一个大于等于给定值的元素

class Solution:
    def bsearch(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        low, high = 0 ,len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] >= val:
                if mid == 0 or nums[mid-1] < val:
                    return mid
                else:
                    high = mid - 1
            else:
                low = mid + 1
        return -1

• 查找最后一个小于等于给定值的元素

class Solution:
    def bsearch(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        low, high = 0 ,len(nums) - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] <= val:
                if mid == len(nums)-1 or nums[mid+1] > val:
                    return mid
                else:
                    low = mid + 1
            else:
                high = mid - 1
        return -1