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

Tag: 二分搜索 LeetCode Posted on 2021-05-25 10:12:27 Edited on 2022-02-05 16:55:16 Views: 550

题目分析

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

二分搜索的变种题,要求 O(log n) 的时间复杂度。

递归法

很直白的解法,第一步先找出一个目标值所在的位置,第二步分别向左向右遍历以找到边界。

其中第一步是 O(log n),第二步在最坏情况下是 O(n),最坏的情况为首尾两端非目标值,其余均为目标值。

但是 LeetCode 依然给让过了。

class Solution {
public:
    vector<int> nums;
    int target;
    
    vector<int> searchRange(vector<int>& nums, int target) {
        this->nums = nums;
        this->target = target;
        vector<int> ans = {-1, -1};
        if (nums.size() == 0) return ans;
        int pos = helper(0, nums.size()-1);
        if (pos == -1) return ans;
        ans[0] = pos;
        ans[1] = pos;
        while(ans[0]-1 >= 0 && nums[ans[0]-1] == target) ans[0]--;
        while(ans[1]+1 < nums.size() && nums[ans[1]+1] == target) ans[1]++;
        return ans;
    }
    
    int helper(int l, int r) {
        if (l > r) return -1;
        if (nums[l] == target) return l;
        if (nums[r] == target) return r;

        int m = (l + r) / 2;
        if (nums[m] == target) return m;
        if (nums[m] > target) {
            return helper(l+1, m-1);
        } else {
            return helper(m+1, r-1);
        }
    }
};

迭代法

首先找 left bound ,当 middle 值等于目标值时,收缩右边界:r = m - 1; 当循环结束时(循环的条件为 l <= r),l 比 r 大 1,因此 l 就是之前 m,即 l 就是 left bound,如果真的存在 target 的话。

因此我们需要检查 l 是否越界。

找到 left bound 后,搜寻 right bound ,这里的一个小优化是新的 l 可以设为 m + 1。

寻找 right bound时,当 middle 值等于目标值时,收缩左边界:l = m + 1; 当循环结束时(循环的条件为 l <= r),r 比 l 小 1,因此 r 就是之前 m,即 r 就是 right bound。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans = {-1, -1};
        // find left bound
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] < target) {
                l = m + 1;
            } else { // num[m] >= target
                r = m - 1;
            }
        }
        if (l >= nums.size() || nums[l] != target) {
            return ans;
        }            
        ans[0] = l;
        // find right bound
        r = nums.size() - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (nums[m] <= target) {
                l = m + 1;
            } else { // nums[m] > target
                r = m - 1;
            }
        }
        ans[1] = r;
        return ans;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/