Last Position of Target
Find the last position of a target number in a sorted array. Return -1 if target does not exist.
Example
Given[1, 2, 2, 4, 5, 5]
.
For target =2
, return 2.
For target =5
, return 5.
For target =6
, return -1.
当找到与target相等的值时,继续向右寻找(start=mid),因为题目要求寻找最后一个index
循环结束判断时,需要先判断A[end],然后再判断A[start]
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 len(A)==0:
return -1
start = 0
end = len(A)-1
while start+1<end:
mid = (start+end)/2
if target >= A[mid]:
start = mid
else:
end = mid
if target == A[end]:
return end
elif target == A[start]:
return start
return -1
Last updated
Was this helpful?