LC1552. Magnetic Force Between Two Balls

class Solution:
    def maxDistance(self, A: List[int], m: int) -> int:
        """  tc O(NlgM) sc O(1), M: diff of max(pos) - min(pos)
        binary search:   range [min-min, max-min], note ball has to be placed in position exists in A 
        intv: minimun distance between any two balls is intv
        main idea: We want to find the maximum d such that count(d) == m.
        """
        A.sort()
        n = len(A)
        def cnt_ball(intv):
            cnt, pos = 1,A[0]
            for i in range(1,n):
                if A[i]-pos >= intv:
                    cnt += 1
                    pos = A[i]
            return cnt 
        l,r = 0, A[-1]-A[0]
        while l < r :
             """
            here to note, if we are trying to look for bisect_right, better mid = r - (r-l)//2 with l = mid, right = mid-1,  if trying to look for bisect_left, using m = l + (r-l)//2 with l = mid-1, r = mid 
            """
            mid = l + (r-l+1)//2 # or r-(r-l)//2  
            if cnt_ball(mid) < m : # inteval is too big 
                r = mid - 1
            else:
                l = mid 
        return l 
                

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()
        def count(d):
            cnt,pre = 1, position[0]
            for i in range(1,n):
                if position[i] - pre >= d:
                    cnt += 1
                    pre = position[i]
                    if cnt >= m:  # optimization: early termination
                        return True 
            return False 
        
        l,r = 0, (position[-1]-position[0])//(m-1)
        while l < r:

            mid = r - (r-l)//2
            if count(mid):# >= m: 
                l = mid
            else:  # mid is too big
                r = mid - 1
        return l