YSMull
<-- algorithm



原题链接

2021/04/12

用True/False 左闭右开模板

找最小的可以直接套模板，找最大的可以转化为「找第一个大于 target 的数」，然后看前一个数是不是 target

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut res = vec![-1, -1];
        let mut l = 0;
        let mut r = nums.len();
        while l < r {
            let mut m = l + (r - l) / 2;
            if nums[m] >= target {
                r = m;
            } else {
                l = m + 1;
            }
        }
        if l < nums.len() && nums[l] == target {
            res[0] = l as i32;
        }

        let mut l = 0;
        let mut r = nums.len();
        while l < r {
            let mut m = l + (r - l) / 2;
            if nums[m] > target {
                r = m;
            } else {
                l = m + 1;
            }
        }
        if l > 0 && nums[l - 1] == target {
            res[1] = (l - 1) as i32;
        }
        return res;
    }
}

闭区间二分查找

impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut res = vec![-1, -1];
        if nums.len() == 0 {
            return res;
        }
        let mut l = 0 as i32;
        let mut r = (nums.len() - 1) as i32;
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m as usize] == target {
                r = m;
            } else if nums[m as usize] > target {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        if l < nums.len() as i32 && nums[l as usize] == target {
            res[0] = l as i32;
        }

        let mut l = 0;
        let mut r = nums.len() - 1;
        while l < r {
            let m = l + (r - l + 1) / 2;
            if nums[m] == target {
                l = m;
            } else if nums[m] > target {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        if l < nums.len() && nums[l] == target {
            res[1] = l as i32;
        }
        return res;
    }
}

二分找第一个，线性找最后一个

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        // 二分结束
        if (l == nums.length // 数组中没有满足性质的点
            || nums[l] != target // 满足性质的点并不是 target
        ) {
            return new int[]{-1, -1};
        }
        // 此时 l 是第一个等于 target 的点
        int l2 = l;
        // 处理 l 已经是最后一个点的情况
        for ( ; l2 < nums.length - 1 && nums[l] == nums[l2 + 1] ; l2++);
        return new int[]{l, l2};
    }
}