用Python编写程序，找到在一条街上点亮所有房屋所需的最小半径

假设我们有一个表示一维线上房屋位置的数字列表叫做nums。现在考虑到我们有3个路灯，我们可以把它们放在线上的任何地方，位于位置x的灯光亮起范围内的所有房子[x-r，x+r]，包括边界。我们必须找到最小的r来使所有房屋都亮起来。

因此，如果输入是nums = [4,5,6,7]，那么输出将是0.5，因为我们可以在4.5，5.5和6.5放置灯具，因此r = 0.5。因此这三盏灯可以照亮所有4个房子。

为了解决这个问题，我们将遵循以下步骤-

定义一个有效函数valid()，这将需要r
last_location：= nums[0] + r
count := 1
将i从0到nums的大小进行循环
- val：=nums[i]
- 如果val – last_location > r, 然后
  - count := count + 1
  - last_location：= val + r
当计数<= 3时，返回true，否则返回false
从主方法执行以下操作-
对列表nums进行排序
left:= 0
right:= nums的最后一个元素
res:= inf
itr:= 0
while left <= right and itr < 20, do
- mid:= left +(right – left) / 2
- 如果valid(mid)是真的，那么
  - res: = min(res， mid)
  - right:= mid
- 否则，
  - left:= mid
  - itr:= itr+1
返回res

示例

让我们看下面的实现以获得更好的理解

class Solution:
   def solve(self, nums):
      def valid(r):
         last_location = nums[0] + r
         count = 1
         for i in range(len(nums)):
            val = nums[i]
            if val - last_location > r:
               count += 1
               last_location = val + r
         return count <= 3
      nums.sort()
      left = 0
      right = nums[-1]
      res = float("inf")
      itr = 0
      while left <= right and itr < 20:
         mid = left + (right - left) / 2
         if valid(mid):
            res = min(res, mid)
             right = mid
         else:
            left = mid
         itr += 1
      return res
ob = Solution()
nums = [4,5,6,7]
print(ob.solve(nums))