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

    
        标签：
        
            二分搜索
        
            LeetCode
        
    发布于：2021-05-25 10:12:27
    编辑于：2022-02-05 16:55:16
    浏览量：1407

题目分析

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;
    }
};

Links: leetcode-34-find-first-and-last-position-of-element-in-sorted-array