6 September 2018: Binary Search

From UMCPC Wiki
Jump to navigation Jump to search

Sagheer and the Nubian Market

  • http://codeforces.com/problemset/problem/812/C
    def cheapestPrice(A, k):
        prices = []
        for i, a in enumerate(A):
            prices.append(a + (i+1)*k)
        prices.sort()
        return sum(prices[:k])
    
    def ok(A, S, k):
        return cheapestPrice(A, k) <= S
    
    n, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    
    k = -1
    skip = n
    while skip >= 1:
        while k+skip <= n and ok(A, S, k + skip):
            k += skip
        skip //= 2
    
    print(k, cheapestPrice(A, k))
    

Kth Smallest Pair Distance

  • https://leetcode.com/problems/find-k-th-smallest-pair-distance/description/
    class Solution {
    public:
        int countPairsWithDifferenceLte(vector<int>& nums, int k) {
            int ans = 0;
            for (auto it = nums.begin(); it != nums.end(); it++) {
                ans += distance(it, upper_bound(it, nums.end(), *it + k)) - 1;
            }
            return ans;
        }
        
        int ok(vector<int>& nums, int k, int x) {
            return countPairsDifferenceLte(nums, x) >= k;
        }
        
        int smallestDistancePair(vector<int>& nums, int k) {
            sort(nums.begin(), nums.end());
            int x = -1;
            for (int b = 1000000; b >= 1; b /= 2) {
                while (!ok(nums, k, x + b)) x += b;
            }
            return x + 1;
        }
    };
    

Implementing Binary Search

Method 1

int lo = 0, hi = n - 1;
while (lo <= hi) {
    int k = (lo + hi) / 2;
    if (array[k] == x) {
        // x found at index k
    }
    if (array[k] > x) {
        hi = k-1;
    } else {
        lo = k+1;
    }
}

Method 2

int k = 0;
for (int skip = n / 2; skip >= 1; skip /= 2) {
    while (k + skip < n && array[k + skip] <= x)) {
        k += skip;
    }
}
if (array[k] == x) {
    // x found at index k
}

Binary Search The Answer

Finding the Smallest Answer

int k = -1;
for (int skip = MAX_K; skip >= 1; skip /= 2) {
    while (!ok(k + skip)) {
        k += skip;
    }
}
k += 1;

Finding the Largest Answer

int k = -1;
for (int skip = MAX_K; skip >= 1; skip /= 2) {
    while (ok(k + skip)) {
        k += skip;
    }
}

References