34.find-first-and-last-position-of-element-in-sorted-array.md

問題

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

回答

初回の回答:

ソート済みの配列から target と同じ要素を見つけ、複数ある場合はその範囲を見つけよという問題。手順としては、

• まず target と同じ要素を二分探索で見つける
• 見つけたらその index を基準に両側を二分探索して始端・終端を見つける

で求められる。以下のコードはパスしたけど、いかんせん手続き的にそのまま書いてるので見通しが悪そう。もうちょいリファクタリングできると思う。

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.len() == 0 {
            return vec![-1, -1]
        }

        let mut l = 0;
        let mut r = nums.len();
        let mut x = None;
        // find the target first
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m] == target {
                x = Some(m);
                break;
            } else if nums[m] > target {
                r = m;
            } else {
                l = m + 1;
            }
        }
        if x.is_none() {
            return vec![-1, -1]
        }

        // find its range for the target
        let i = x.unwrap();
        let mut start = l;
        let mut end = r;

        // find start
        l = 0;
        r = i;
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m] == target {
                r = m;
            } else {
                l = m + 1;
            }
        }
        start = l;

        // find end
        l = i + 1;
        r = nums.len();
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m] == target {
                l = m + 1;
            } else {
                r = m;
            }
        }
        end = l - 1;
        vec![start as i32, end as i32]
    }
}

二回目の回答:

二分探索、始端・終端探索をそれぞれ binary_search と find_bound に分けてみたけど、あんまりコード量変わらなかった。

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.len() == 0 {
            return vec![-1, -1]
        }

        fn binary_search(nums: &Vec<i32>, target: &i32) -> i32 {
            let mut l = 0;
            let mut r = nums.len();
            while l < r {
                let mut m = l + (r - l) / 2;
                match nums[m].cmp(target) {
                    std::cmp::Ordering::Equal => return m as i32,
                    std::cmp::Ordering::Greater => r = m,
                    std::cmp::Ordering::Less => l = m + 1
                }
            }
            -1
        }

        fn find_bound(nums: &Vec<i32>, target: &i32, target_index: &i32, go_left: bool) -> i32 {
            if go_left {
                let mut l = 0;
                let mut r = *target_index as usize;
                while l < r {
                    let m = l + (r - l) / 2;
                    match nums[m].cmp(target) {
                        std::cmp::Ordering::Equal => r = m,
                        _ => l = m + 1,
                    }
                }
                return l as i32
            }

            let mut l = *target_index as usize;
            let mut r = nums.len();
            while l < r {
                let m = l + (r - l) / 2;
                match nums[m].cmp(target) {
                    std::cmp::Ordering::Equal => l = m + 1,
                    _ => r = m,
                }
            }
            (l - 1) as i32
        }

        let target_index = binary_search(&nums, &target);
        if target_index == -1 {
            return vec![-1, -1]
        }

        let start = find_bound(&nums, &target, &target_index, true);
        let end = find_bound(&nums, &target, &target_index, false);
        vec![start, end]
   }
}