題目：在一個(gè)排序數(shù)組（從小到大）中找一個(gè)數(shù)达址，返回該數(shù)出現(xiàn)的最后一個(gè)位置赫段，如果不存在舵抹，返回-1
給出數(shù)組 [1, 2, 2, 2,4, 5, 5]
對(duì)于 target = 2, 返回 3.
對(duì)于 target = 5, 返回 6.
對(duì)于 target = 6, 返回 -1.
解題思路：
在二分搜索上做改進(jìn)。
遞歸實(shí)現(xiàn)：
def last_position(array,low,high,key):
mid = int((high-low)/2 + low)
if low > high :
return -1
if low == high:#說(shuō)明范圍已經(jīng)縮小到一個(gè)數(shù)（這樣處理是為了防止數(shù)組越界）
return low
elif array[mid] > key:
return last_position(array,low,mid-1,key)
elif array[mid] < key:
return last_position(array,mid+1,high,key)
elif array[mid+1] == key:#不是最后一個(gè)位置鉴分，所以要接著搜索
return last_position(array,mid+1,high,key)
else:
return mid
循環(huán)實(shí)現(xiàn)：
def lastPosition(A, target):
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
