Find chunk index in buffer of chunks using binary search algorithm.

binary_search.rs

fn main() {

    // vector of data built from 4-bytes chunks
    let mut buf = vec![];
    buf.extend(1u32.to_be_bytes());
	buf.extend(10u32.to_be_bytes());
    buf.extend(20u32.to_be_bytes());
    buf.extend(47u32.to_be_bytes()); // searching for this one
    buf.extend(59u32.to_be_bytes());
    buf.extend(63u32.to_be_bytes());

    // chunk that we are search for
    let target = 46u32.to_be_bytes();

    // chunks are u32 thus 4 bytes
    let chunk_size = 4;
    
    // find the closest index using binary search
    let index = binary_search(&buf, chunk_size, &target);
    println!("closest: {:?}", index);
}

/// Search `target_value` chunk of size `chunk_size` in `buf` of chunks.
pub fn binary_search(buf: &[u8], chunk_size: usize, target_value: &[u8]) -> (usize, bool) { // (index, found)
    let len = buf.len() / chunk_size;

    let mut low: i8 = 0; // first index
    let mut high: i8 = len as i8 - 1; // last index

    let mut mid_index = 0; // current middle

    while low <= high {
        let mid = ((high - low) / 2) + low;
        mid_index = mid as usize;
        println!("mid_index: {}", mid_index);
        
        let start = mid_index * chunk_size;
        let end = start + chunk_size;
        let val = &buf[start..end];

        if val == target_value {
            return (mid_index, true);
        }

        if val < target_value {
            low = mid + 1;
        }
        if val > target_value {
            high = mid - 1;
        }
    }
    
    (if mid_index > 0 {
        mid_index - 1
    } else {
        0
    }, false)
}