786 binary search

class Solution:
    def kthSmallestPrimeFraction(self, A: List[int], K: int) -> List[int]:
        low = A[0] / A[-1]
        high = 1
        res = 0

        def less_than_or_eq_k(x):
            count = 0
            p_best = None
            q_best = None
            l = -1
            r = 1
            while r < len(A):
                while A[l+1] <= A[r] * x:
                    l += 1
                count += l + 1
                if l >= 0:
                    if p_best is None or A[p_best] / A[q_best] < A[l] / A[r]:
                        p_best = l
                        q_best = r
                r += 1
            return count, p_best, q_best

        while high - low > 1e-07:
            mid = low + (high - low) / 2.0
            count, p, q = less_than_or_eq_k(mid)
            if count > K:
                high = mid
            else:
                low = mid
                res = (A[p], A[q])

        return res