原题
在一个排序数组中找一个数，返回该数出现的最后一个位置，如果不存在，返回-1
给出数组 [1, 2, 2, 4, 5, 5]
- 对于 target = 2, �返回 2.
- 对于 target = 5, �返回 5.
- 对于 target = 6, �返回 -1.
解题思路
- 二分法，对于找最后一个位置的要求：只有target大于A[end]才会
end = mid
完整代码
class Solution:
# @param {int[]} A an integer array sorted in ascending order
# @param {int} target an integer
# @return {int} an integer
def lastPosition(self, A, target):
# Write your code here
if not A:
return -1
start, end = 0, len(A) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] <= target:
start = mid
else:
end = mid
if A[end] == target:
return end
if A[start] == target:
return start
return -1
