34. Find First and Last Position of Element in Sorted Array

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

直接使用一次 findFirstIndex + FindLastIndex 就可以完成

---

impl Solution {
      pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        vec![Solution::find_index(&nums, target, true), Solution::find_index(&nums, target, false)]
    }
 
    fn find_index(nums: &Vec<i32>, target: i32, first: bool) -> i32 {
        // classic binary search
        let mut ans = -1;
        let mut left = 0;
        let mut right = nums.len() as i32 - 1;
        while left <= right {
            let mid = left + (right - left) / 2;
            if nums[mid as usize] < target {
                left = mid + 1;
            } else if nums[mid as usize] > target {
                right = mid - 1;
            } else {
                // 向左还是向右逼近
                if first {
                    right = mid - 1;
                    ans = mid;
                } else {
                    left = mid + 1;
                    ans = mid;
                }
            }
        }
        ans
    }
}

或者直接使用 Rust 自己查找元素的方法 ， 自定义判断条件，更加的直观，但是达不到考察的目的

    fn search_range_other_way(nums: &Vec<i32>, target: i32) -> Vec<i32> {
        let left = nums.partition_point(|x| x < &target);
        if left == nums.len() || nums[left] != target {
            return vec![-1, -1];
        }
 
        let right = nums.partition_point(|x| x <= &target);
        return vec![left as i32, right as i32 - 1];
    }

#算法/二分