競プロ典型 007

https://atcoder.jp/contests/typical90/tasks/typical90_g

二分探索で対象の値より小さくても最も大きい値の位置を探します。

// CP Classes
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (Vec<i32>, usize) {
    let _N: usize = read();
    let A: Vec<i32> = read_vec();
    let Q: usize = read();
    (A, Q)
}

fn binary_search(B: i32, A: &[i32]) -> usize {
    if A.len() == 1 {
        return 0
    }
    
    let mid = A.len() / 2;
    if A[mid] < B {
        binary_search(B, &A[mid..]) + mid
    }
    else {
        binary_search(B, &A[..mid])
    }
}

fn F_each(B: i32, A: &Vec<i32>) -> i32 {
    let i = binary_search(B, &A[..]);
    if i == A.len() - 1 {
        (B - A[i]).abs()
    }
    else {
        min((B - A[i]).abs(), (A[i+1] - B).abs())
    }
}

fn F(mut A: Vec<i32>, Q: usize) {
    A.sort();
    for _ in 0..Q {
        let B: i32 = read();
        println!("{}", F_each(B, &A))
    }
}

fn main() {
    let (A, Q) = read_input();
    F(A, Q)
}