[已解决]算法题-目标最后位置-last Position

哲子DZ

题目要求：给一个升序数组，找到target最后一次出现的位置，如果没出现过返回-1；例：给出 [1, 2, 2, 4, 5, 5]，target = 2, 返回 2.target = 5, 返回 5.
target = 6, 返回 -1.
先给出正确算法：

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):
        if not A or target is None:
            return -1
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if A[mid] < target:
                start = mid
            elif A[mid] > target:
                end = mid
            else:
                start = mid
        if A[end] == target:
            return end
        elif A[start] == target:
            return start
        else:
            return -1

下面是我写的代码：

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):
        if not A or target is None:
            return -1
        start, end = 0, len(A) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if A[mid] > target:
                end = mid
            else:
                start = mid
        if A[start] == target:
            return start
        elif A[end] == target:
            return end
        return -1

我写的代码错误信息是：输入信息：A为[1,2,2,4,5,5], target为5，应该返回5，但是代码返回4.
我的问题：在我看来和答案代码的区别是在（1）if判断时大于和小于是颠倒的，（2）还有少了一个elif语句。
第（1）个问题想不明白，第（2）个问题，A[mid] > target的其他情况不就是A[mid] < target吗？为什么还要加elif？考虑A[mid] == target?如果考虑的是相等的情况，为什么第一个if里的条件不是>=？
以上，不知道我的问题有没有描述情书，谢谢大家！辛苦了！

最佳答案

月排行榜 / 总排行榜

冬雪雪冬

2017-8-16 22:47:39

本题就是采用折半查找法。先把start和end设为两端，mid为中间，如果A[mid]<target就说明再后一半中，把start改为mid，否则在前一半，把end改为mid，逐渐缩小范围得到答案。这就是前面程序的思路。

我的问题：在我看来和答案代码的区别是在（1）if判断时大于和小于是颠倒的，#这个没关系
（2）还有少了一个elif语句。
第（1）个问题想不明白，第（2）个问题，A[mid] > target的其他情况不就是A[mid] < target吗？为什么还要加elif？考虑A[mid] == target?如果考虑的是相等的情况，为什么第一个if里的条件不是>=？#比如有10个数字5，到A[mid] == target时，按你的>=还会继续折半，就不会得到最后一个5了。

跳转到最佳答案楼层

冬雪雪冬

本题就是采用折半查找法。先把start和end设为两端，mid为中间，如果A[mid]<target就说明再后一半中，把start改为mid，否则在前一半，把end改为mid，逐渐缩小范围得到答案。这就是前面程序的思路。

我的问题：在我看来和答案代码的区别是在（1）if判断时大于和小于是颠倒的，#这个没关系
（2）还有少了一个elif语句。
第（1）个问题想不明白，第（2）个问题，A[mid] > target的其他情况不就是A[mid] < target吗？为什么还要加elif？考虑A[mid] == target?如果考虑的是相等的情况，为什么第一个if里的条件不是>=？#比如有10个数字5，到A[mid] == target时，按你的>=还会继续折半，就不会得到最后一个5了。

ba21

if A[mid] > target:  
                end = mid   #因为这里先满足的是end 所以，后面要先返回end(因为你start也有值，end也有值，顺序不对的话，返回的数据就不对了。)
            else:
                start = mid  

  if A[end] == target:
            return end
        elif A[start] == target:
            return start

jerryxjr1220

这题倒序查找不是更好吗？倒序查找到的第一个就是答案，不然就返回-1

冬雪雪冬

jerryxjr1220 发表于 2017-8-16 23:16
这题倒序查找不是更好吗？倒序查找到的第一个就是答案，不然就返回-1

数据量大时，折半查找效率会高些。

哲子DZ

==问题清楚了，自己加了代码还是有问题，我自己再想一下，要是不能解决再向您请教，谢谢！！

哲子DZ

ba21 发表于 2017-8-16 22:56
if A[mid] > target:  
                end = mid   #因为这里先满足的是end 所以，后面要先返回end(因 ...

好的，明白了，谢谢您！