Jianbo Dai's

jz053I.在排序数组中查找数字

 
  • Oct 13, 2020

题目链接

既然输入的数组是排序的，那么我们就能很自然地想到用二分查找算法。在题目给的例子中，我们可以先用二分查找找到一个3，由于3可能出现多次，因此我们找到的3的左右两边可能都有3，于是在找到的3的左右两边顺序扫描，分别找出第一个3和最后一个3。因为要查找的数字在长度为n的数组中有可能出现O（N）次，所以顺序扫描的时间复杂度是O（N），这种算法的效率与直接从头到尾顺序扫描整个数组统计3出现的次数方法是一样的，显然我们可以有更加高效的算法。

我们思考如何更好地利用二分法查找算法，假设我们要统计数字k在排序数组中出现的次数。在前面的算法中，时间主要消耗在如何确定重复出现的数字的第一个k和最后一个k的位置上，有没有可能用二分查找直接找到第一个和最后一个k呢。

我们先复习如何用二分查找在数组中找到第一个k。二分查找算法总是先拿数组中中间的数字和k做比较，如果中间的数字比k大，那么k只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。反之，我们在数组的后半段查找。如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k，如果中间数字的前一个数字不是k，那么此时中间的数字刚好就是第一个k；如果中间数字的前面一个数字也是k那么说明第一个k肯定在数组的前半段，下一轮我们仍需要在数组的前半段查找。基于这种思路我们可以写出如下代码。这个算法的时间复杂度是O（logN），空间复杂度是O（1）。当然，第一种方法仍然有点臃肿，我们可以合并两个二分查找的过程，并且转换思路为查找插入target和target-1的位置（若和数组中的数字相同则插入到右边），这样可以分别找到要找的数字序列的起点和终点，代码实现如3所示。

class Solution:
    def search1(self, nums: List[int], target: int) -> int:
        num = 0
        def getfirstk(nums, target, start, end):
            if start > end:
                return -1
            mid = (start + end) // 2
            midnum = nums[mid]
            if midnum == target:
                if (mid > 0 and nums[mid-1] != target) or mid == 0:
                    return mid
                else:
                    end = mid - 1
            elif midnum < target:
                start = mid + 1
            else:
                end = mid - 1
            return getfirstk(nums, target, start, end)
                  
        def getlastk(nums, target, start, end):
            if start > end:
                return -1
            mid = (start + end) // 2
            midnum = nums[mid]
            if midnum == target:
                if (mid < len(nums)-1 and nums[mid+1] != target) or mid == len(nums)-1:
                    return mid
                else:
                    start = mid + 1
            elif midnum > target:
                end = mid - 1
            else:
                start = mid + 1
            return getlastk(nums, target, start, end)

        kfirst = getfirstk(nums, target, 0, len(nums)-1)
        klast = getlastk(nums, target, 0, len(nums)-1)

        if kfirst > -1 and klast > -1:
            num = klast - kfirst + 1
        return num

    def search2(self, nums: List[int], target: int) -> int:
        start, end = 0, len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] >= target:
                end = mid -1
            else:
                start = mid + 1
        kfirst = end
        # 查找完左边界后，右边界一定在闭区间[end,len(nums)-1] 中，因此直接从此区间开始二分查找即可。
        end =  len(nums) - 1
        while start <= end:
            mid = (start + end) // 2
            if nums[mid] <= target:
                start = mid + 1
            else:
                end = mid - 1
        klast = start

        return klast - kfirst - 1

    def search3(self, nums: [int], target: int) -> int:
        def helper(tar):
            i, j = 0, len(nums) - 1
            while i <= j:
                m = (i + j) // 2
                if nums[m] <= tar: i = m + 1
                else: j = m - 1
            return i
        return helper(target) - helper(target - 1)
Search