Solution of https://leetcode.com/problems/median-of-two-sorted-arrays/

median_of_two_sorted_arrays.rs

use std::cmp;


pub fn smaller(vec: &Vec<i32>, val: i32) -> i32 {
    let len = vec.len();
    if(len == 0) {
        return 0;
    }
    if vec[len - 1] < val {
        return len as i32;
    } else if val <= vec[0] {
        return 0;
    }
    let (mut low, mut high) = (0, len as i32 - 1);
    while high - low > 1 {
        let mid: i32 = (low + high) / 2;
        if vec[mid as usize] < val {
            low = mid;
        } else {
            high = mid;
        }
    }
    
    low + 1
}


pub fn bigger(vec: &Vec<i32>, val: i32) -> i32 {
    let len = vec.len();
    if(len == 0) {
        return 0;
    }
    if val < vec[0] {
        return len as i32;
    } else if vec[len - 1] <= val {
        return 0;
    }
    
    let (mut low, mut high) = (0, len as i32 - 1);
    while high - low > 1 {
        let mid: i32 = (low + high) / 2;
        if val < vec[mid as usize] {
            high = mid;
        } else {
            low = mid;
        }
    }
    
    len as i32 - high
}




pub fn get_values(vec1: &Vec<i32>, vec2: &Vec<i32>, val: i32) -> (i32, i32, i32, i32) {
    (smaller(&vec1, val), bigger(&vec1, val), smaller(&vec2, val), bigger(&vec2, val))
}


pub fn get_answer(vec1: &Vec<i32>, vec2: &Vec<i32>, l1: i32, l2: i32, target: i32, el: i32) -> f64 {
    let (len1, len2) = (vec1.len(), vec2.len());
    
    println!("len1: {}, len2: {}, l1: {}, l2: {}, target: {}, el: {}", len1, len2, l1, l2, target, el);
    if (len1 + len2) % 2 == 1 {
        return el as f64;
    }
    if target + 1 < l1 + l2 {
        el as f64
    } else {
        if len1 as i32 + len2 as i32 - l1 - l2 > target {
            return el as f64;   
        }
        if cmp::min(l1, l2) > 0 {
            (el as f64 + cmp::min(vec2[len2 - l2 as usize], vec1[len1 - l1 as usize]) as f64) / 2.0
        } else if l1 != 0 {
            (el as f64 + vec1[len1 - l1 as usize] as f64) / 2.0
        } else if l2 != 0 {
            (el as f64 + vec2[len2 - l2 as usize] as f64) / 2.0
        } else {  // Happens when "el" is also the largest element
            el as f64
        }
    }
}


pub fn check(s1: i32, l1: i32, s2: i32, l2: i32, len1: usize, len2: usize, target: i32) -> bool {
    println!("s1: {}, l1: {}, s2: {}, l2: {}, len1: {}, len2: {}, target: {}", s1, l1, s2, l2, len1, len2, target);
    if (len1 + len2) % 2 == 1 {
        cmp::max(s1 + s2, l1 + l2) < target
    } else {
        s1 + s2 < target && l1 + l2 - 1 < target
    }
}


impl Solution { 
    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
        let (mut len1, mut len2, mut value) = (nums1.len(), nums2.len(), 0);
        let target: i32 = (len1 as i32 + len2 as i32 + 1) / 2;
        println!("target: {}", target);
        for i in 0..2 {
            let mut low: usize = 0;
            if i == 0 && len1 == 0 || i == 1 && len2 == 0 {
                continue;
            }
            let mut high: usize = if i == 0 {
                len1 - 1
            } else {
                len2 - 1
            };
            println!("i: {}", i);
            
            while high - low > 1 {
                let mid: usize = (low + high) / 2;
                let el = if i == 0 {
                    nums1[mid]
                } else {
                    nums2[mid]
                };
                println!("low: {}, high: {}, mid: {}, el: {}", low, high, mid, el);
                let (s1, l1, s2, l2) = get_values(&nums1, &nums2, el);
                if check(s1, l1, s2, l2, len1, len2, target) {
                    return get_answer(&nums1, &nums2, l1, l2, target, el);   
                }
                if s1 + s2 >= target {
                    high = mid;
                } else {
                    low = mid
                }
            }
            for which in vec![low, high].into_iter() {
                let el = if i == 0 {
                    nums1[which]
                } else {
                    nums2[which]
                };
                println!("which: {}, el: {}", which, el);
                let (s1, l1, s2, l2) = get_values(&nums1, &nums2, el);
                if check(s1, l1, s2, l2, len1, len2, target) {
                    return get_answer(&nums1, &nums2, l1, l2, target, el);
                }
            }
        }
        
        0.0
    }
}