二分 & 三分

• OI Wiki: https://oi-wiki.org/basic/binary/

题目	难度
2448. 使数组相等的最小开销	中等	T3 三分
Abc279_d		三分

二分

Golang：

SearchInts

func SearchInts(a []int, x int) int {
	return Search(len(a), func(i int) bool { return a[i] >= x })
}

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

C++：

std::lower_bound

Java：

    private int binarySearchLeftBound(boolean[] nums) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 边界二分 F, F,..., F, [T, T,..., T]
            // ----------------------^
            if (checkMid(nums, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

三分

    private long ternarySearch_u(int mn, int mx) {
        long l = mn, r = mx;
        while (r - l > 2) {
            long m1 = (l * 2 + r) / 3;
            long m2 = (l + r * 2) / 3;
            if (f(m1) > f(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }
        long res = f(l);
        for (long i = l + 1; i <= r; i++) {
            res = Math.min(res, f(i));
        }
        return res;
    }

    private long f(long mid) {
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            res += Math.abs(nums[i] - mid) * cost[i];
        }
        return res;
    }

2448. 使数组相等的最小开销

import java.util.Arrays;

public class Solution2448 {
    private int[] nums;
    private int[] cost;

    public long minCost(int[] nums, int[] cost) {
        this.nums = nums;
        this.cost = cost;
        int min = Arrays.stream(nums).min().orElseThrow();
        int max = Arrays.stream(nums).max().orElseThrow();
        return ternarySearch_u(min, max);
    }

    private long ternarySearch_u(int mn, int mx) {
        long l = mn, r = mx;
        while (r - l > 2) {
            long m1 = (l * 2 + r) / 3;
            long m2 = (l + r * 2) / 3;
            if (f(m1) > f(m2)) {
                l = m1;
            } else {
                r = m2;
            }
        }
        long res = f(l);
        for (long i = l + 1; i <= r; i++) {
            res = Math.min(res, f(i));
        }
        return res;
    }

    private long f(long mid) {
        long res = 0;
        for (int i = 0; i < nums.length; i++) {
            res += Math.abs(nums[i] - mid) * cost[i];
        }
        return res;
    }
}

（全文完）