Binary Search to find cross indices

Aug. 4, 2024

I've included an example of a Zig implementation code for a binary search algorithm to find cross indices between two arrays. The problem consists in finding positions where values for two ordered arrays meet the condition that $y_i \leq x_i \wedge y_{i + 1} > x_{i + 1}$.

This problem is constrained to the first value of $y$ is less than the first value of $x$, and at the same time, the last value of $y$ is greater than the last value of $x$. Because of that, it is guaranteed that at least one index will be found.

Below is the body of the search function, which is called recursively until complete space of values is evaluated.

/// Look for indices which search criteria is true for.
///
/// Arguments:
///
///     T : type of data parameters
///     res : an array list to return results
///     x : first array
///     y : second array
///     left : left index position to start the search
///     right : right index position to end the search
///
/// Assumptions:
///     
///     left < right
///     x.len == y.len
///     y[0] < x[0]
///     y[y.len - 1] > x[x.len - 1]
///
/// Return:
///
///     void or error
pub fn crossindex(T: type, res: *std.ArrayList(u64), x: []T, y: []T, left: u64, right: u64) !void {
    // Checking error conditions
    if (left >= right) return CrossIndexError.ArraysWithDifferentSize;
    if (x.len != y.len) return CrossIndexError.InvalidIndices;
    // Computing middle index
    const mid = left + (right - left) / 2;
    // Evaluating search condition
    if ((y[mid] <= x[mid]) and (y[mid + 1] > x[mid + 1])) {
        try res.append(mid);
    }
    // Recursing search on the left and right sides
    if (mid - left >= 1) {
        try crossindex(T, res, x, y, left, mid);
        try crossindex(T, res, x, y, mid + 1, right);
    }
}

A more detailed explaination for this problem and the full implementation can be found in this link.