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.

  1. 当找到与target相等的值时,继续向右寻找(start=mid),因为题目要求寻找最后一个index

  2. 循环结束判断时,需要先判断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?