行情好起来了，连续拿到两个offer。。_

来源：编程网事

大家好，我就是那个在B站讲算法的「华南溜达虎」。

今天在脉脉上看到一位同学表示找了一年的工作，终于在上周连续通过两家公司的面试，不禁感慨行情慢慢好起来了。

言归正传，今天我们来分享一道的面试原题「在排序数组中查找元素的第一个和最后一个位置」。

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

思路解析

最简单直观的方法就是遍历一遍数组记录target的起始位置和结束位置，这种方法的时间复杂度为O(n)，题目要求时间复杂度为O(logn)。

给定的数组是有序的，还要求时间复杂度为O(logn)，自然而然就想到二分查找。这里我们寻找target对应的左右边界需要进行两次二分查找。

假设给定的nums = [5,7,7,8,8,10]，target = 8，下面来看下寻找8对应左边界的过程。

1. 初始化left=0， right=5，中间位置mid=2对应的元素小于target=8，所以我们需要去mid右边绿色的区域寻找target。

2. 当前mid位置的值等于target=8，我们记录下当前的索引index=4。然后继续去mid左边查找target。

3. 当前mid位置的值等于target=8，更新index=3，继续去mid左边查找target。。

4. 此时left>right，我们就拿到了左边界的索引index。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = binSearch(nums, target, true);
        int right = binSearch(nums, target, false);
        return {left, right};
    }

    //isLeft表示是否寻找左边界
    int binSearch(vector<int>& nums, int target, bool isLeft) {
        int left = 0, right = nums.size() - 1;
        int index = -1;
        while (left <= right) {
            int mid = (left + right)/2;
            //mid位置的值比目标值大，需要去mid左边寻找目标值
            if (nums[mid] > target) {
                right = mid - 1;
            //mid位置的值比目标值小，需要去mid右边寻找目标值
            } elseif (nums[mid] < target) {
                left = mid + 1;
            } else {
                //找到目标值,先记录下当前的索引
                index = mid;
                if (isLeft) {
                    //如果寻找左边界，需要继续去mid左边更新index的值
                    right = mid - 1;
                } else {
                    //如果寻找右边界，需要继续去mid右边更新index的值
                    left = mid + 1;
                }
            }
        }
        return index;
    }
};

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = self.binSearch(nums, target, True)
        right = self.binSearch(nums, target, False)
        return [left, right]

    # isLeft表示是否寻找左边界
    def binSearch(self, nums, target, isLeft):
        left, right = 0, len(nums) - 1
        index = -1
        while left <= right:
            mid = (left + right) // 2
            # mid位置的值比目标值大，需要去mid左边寻找目标值
            if nums[mid] > target:
                right = mid - 1
            # mid位置的值比目标值小，需要去mid右边寻找目标值
            elif nums[mid] < target:
                left = mid + 1
            else:
                # 找到目标值,先记录下当前的索引
                index = mid
                if isLeft:
                    # 如果寻找左边界，需要继续去mid左边更新index的值
                    right = mid - 1
                else:
                    # 如果寻找右边界，需要继续去mid右边更新index的值
                    left = mid + 1
        return index

特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。