pythontip 100days-day20

Code › python
, ,

题目

输入一个升序的整数数组，和一个整数，使用二分查找在数组中搜索该整数，返回最靠右的位置。

如果不存在返回-1

例子

binarySearchRightmost([1,2,3,3,3,4],3) -> 4
binarySearchRightmost([10,14,20,21,22,22],22) -> 5
binarySearchRightmost([5,10,12],3) -> -1

假设

  1. 输入的数组不为空
  2. 输入的数组为升序

tips

  1. 二分查找变形

答案

解法1

def binarySearchRightmost(nums,target):
    rightmost_idx = -1
    left , right = 0 , len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            rightmost_idx = mid
            left = mid + 1
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1 
    return rightmost_idx

性能：

  1. 时间复杂度O(logn)
  2. 空间复杂度O(1)

关键点：1.二分查找变形

解法2：

def binarySearchRightmost(nums: list, target: int) -> int:
    if not nums:
        return -1
    i, j = 0, len(nums) - 1
    while i <= j:
        m = (i + j) // 2
        if target == nums[m]:
            """
            1. 如果nums[m] == target，但是存在nums[m+1] == target，则应该继续判断
            2. 将j作为右边界，控制m不会越界
            """
            if m < j:
                if nums[m + 1] > nums[m]:
                    return m
                else:
                    i = m + 1
            else:
                return m

        elif target < nums[m]:
            j = m - 1
        else:
            i = m + 1

    return -1