在数组时间复杂度

Question

下面给出了问题陈述和解决方案。我无法理解解决方案背后的逻辑。

问题陈述:
给定一个数组包含n+1个整数，其中每个整数介于1和n之间，证明至少存在一个重复的数字。假设只有一个重复的数字，找到重复的一个。

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 1
        high = len(nums)-1

        while low < high:
            mid = low+(high-low)/2
            count = 0
            for i in nums:
                if i <= mid:
                    count+=1
            if count <= mid:
                low = mid+1
            else:
                high = mid
        return low

首先，搜索空间是1到n之间的数字。每次我选择一个数字mid（它是中间的那个），并计算所有等于或小于mid的数字。如果计数大于mid，则搜索空间为[1 mid]，否则为[mid+1n]。我这样做，直到搜索空间只有一个数字。

假设n=10，我选择mid=5。然后我对数组中小于等于MID的所有数字进行计数。如果有超过5个小于5的数字，那么根据鸽子洞原则(https://en.wikipedia.org/wiki/Pigeonhole_principal)，其中一个已经发生了不止一次。所以我将搜索空间从[110]缩小到[15]。否则，重复的数字在后半部分，因此对于下一步，搜索空间将是[610]。

疑问：在上面的解决方案中，当count<=mid时，为什么要将low更改为low=mid+1或将high=mid更改为low=mid？背后的逻辑是什么？

我无法理解这个算法背后的逻辑

相关链接:https://discuss.leetcode.com/topic/25580/two-solutions-with-explaination-o-nlog-n-and-o-n-time-o-1-space-noth-change-the-input-array

Answer 1

这是一个二分搜索。您正在将搜索空间削减一半并重复。

这样考虑一下：您有一个包含101项的列表，并且您知道它包含值1-100。走到一半，50。计算有多少项小于或等于50。如果有超过50项小于或等于50项，则重复项在0-50范围内，否则重复项在51-100范围内。

二分搜索只是将范围减半。看0-50，取中点25，重复。

inspection_count=0
for i in nums:
    inspection_count+=1
    if i <= mid:
        count+=1

p = 0, q = 5, n = 10
"I have ten values, and every value is between zero and five.
At least one of these values must be duplicated."

我们可以概括这一点，但一个更有效和相关的例子是

p = 50, q = 99, n = 50
"I have a collection of fifty values, and every value is between fifty and ninety-nine.
There are only forty nine *distinct* values in my collection.
Therefore there is a duplicate."