'''
第20天：二分查找最右
每日一题 夸克编程 昨天
题目
输入一个升序的整数数组，和一个整数，使用二分查找在数组中搜索该整数，返回最靠右的位置。
如果不存在返回-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
假设
输入的数组不为空
输入的数组为升序
'
'''
def binarySearch(nums, left, right, target):
if left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif nums[mid] < target:
binarySearch(nums, mid+1, right, target)
else:
binarySearch(nums, left, mid-1, target)
return 0
def binarySearchRightmost(nums, target):
index = -1
if target < nums[0] or target > nums[-1]:
return -1
if target == nums[-1]:
return len(nums)-1
index = binarySearch(nums, 0, len(nums)-1, target)
while index+1 < len(nums)-1 and nums[index] == nums[index+1]:
index += 1
return index
print(binarySearchRightmost([1,2,3,3,3,4],3))# -> 4
print(binarySearchRightmost([1,2,3,3,3,4],1))# -> 4
print(binarySearchRightmost([10,14,20,21,22,22],22))# -> 5
print(binarySearchRightmost([5,10,12],3))# -> -1
print(binarySearchRightmost([5],7))# -> -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
性能：
时间复杂度O(logn)
空间复杂度O(1)
