Potential issue with final step in search algorithm

[foresterre]

See foresterre/cargo-msrv#288

[bbannier]

I do not really understand this issue, but wonder whether I have run into it as well. I see a bisect converge on a value with never passed the check in the convergence function (and I believe I set a correct converge behavior).

use std::sync::LazyLock;

use bisector::{Bisector, ConvergeTo, Indices, Step};

// We bisect the smallest prefix of `XS` for which `check` still returns true.
fn f(i: usize) -> ConvergeTo<usize, usize> {
    if check(i) {
        ConvergeTo::Left(i)
    } else {
        ConvergeTo::Right(i)
    }
}

/// Returns true if sum of the first `idx` elements of `XS` is smaller than 6.
fn check(idx: usize) -> bool {
    let sum: u32 = XS.iter().take(idx).sum();
    let check = sum < 6;
    eprintln!("{idx}: {check}",);

    check
}

static XS: LazyLock<Vec<u32>> = LazyLock::new(|| (0..10).collect::<Vec<u32>>());

fn main() {
    let indices: Vec<_> = (0..XS.len()).rev().collect();

    eprintln!("INITIAL CHECK");
    assert!(
        indices.iter().any(|&x| check(x)),
        "check dones not pass for any give index"
    );

    let bisector = Bisector::new(indices.as_slice());
    let mut elements_seen = vec![];
    let mut value = None;

    eprintln!("BISECTING");

    let mut i = Indices::from_bisector(&bisector);
    while let Step {
        indices,
        result: Some(t),
    } = bisector.bisect(|&v| f(v), i)
    {
        i = indices;

        let val = match t {
            ConvergeTo::Left(l) => l,
            ConvergeTo::Right(r) => r,
        };

        elements_seen.push(val);
        value = Some(val);
    }

    // With the hardcoded values we should have converged.
    let idx = value.unwrap();
    eprintln!("DONE: converged on {idx}");
    assert!(check(idx), "converged on {idx} which does not pass check");
}

This produces the following output

$ foo
INITIAL CHECK
9: false
8: false
7: false
6: false
5: false
4: false
3: true
BISECTING
5: false
2: true
3: true
4: false
DONE: converged on 4
4: false
thread 'main' panicked at src/main.rs:60:5:
converged on 4 which does not pass check
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Is this the same issue? I see foresterre/cargo-msrv#290 is still open, but wonder whether there might be a workaround, e.g., does this always affect the last value in which case I could store all visited values and then find the last passing one (expensive 🤷)?

[bbannier]

Looking into it some more, at least my issue seems to be due to how Indices::middle will always pick the left side due to use of integer division which rounds left, https://github.com/foresterre/bisector/blob/.

bisector/src/lib.rs

Lines 250 to 262 in d0e25bd

	/// Computes the mid-point between the left and right indices.
	/// Uses integer division, so use with care.
	#[inline]
	pub fn middle(&self) -> usize {
	debug_assert!(
	self.right >= self.left,
	"right index ({}) < left index ({}), but expected right index >= left index",
	self.right,
	self.left,
	);
	self.left + ((self.right - self.left) / 2)
	}

I tried implementing a fix by making middle indicate that it was operation on a view with an even number of elements by returning both possible middles, but ran into some issues. To break the tie I needed to change the convergence function from FnOnce to Fn so I could it invoke it for both middle elements. This makes it possible to handle cases where both middles want to go in the same direction. At least in what I tried other cases would require that both sides of Side have the same type.

I would be willing drive a fix to completion, but I think I would need some help.

[foresterre]

Thanks for the confirmation! I'll have a deeper look later this week.

My initial thought is that my implementation is either bisect left xor bisect right (1), and we als need the other one.

(1) https://docs.python.org/3/library/bisect.html