'''
第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)
