Linear scan array from left to right or from right to left.

Find the first index with given value. A trivial optimization here is when we find current element is greater than target(search left to right), we won’t search the left elements.

Time complexity: $O(N)$

classSolution { public: vector<int> searchRange(vector<int>& nums, int target){ vector<int> res; int le = -1, ri = -1;

Naive approach will not meet the challenge requirement. We can use the approach of binary search, but it’s a variant of original binary-search.

Take search first left position for example, When we got an index(suppose idx) where value equal target, we store the current position and safely ignore the right part [idx ~ ..] of the array, so we update the hi pivot.

Search last right position is similar.

Time complexity: $O(logN)$.

#include<vector> usingnamespacestd;

classSolution { public: intsearch(vector<int>& A, int target, bool search_left){ int lo = 0, hi = A.size()-1; int ans = -1; while(lo <= hi) { int mid = (lo + hi) / 2; if(A[mid] < target) lo = mid + 1; elseif(A[mid] > target) hi = mid - 1; else { ans = mid; // find first left if(search_left) hi = mid - 1; else lo = mid + 1; } } return ans; }

vector<int> searchRange(vector<int>& nums, int target){ vector<int> res; int left = search(nums, target, true); res.push_back(left); if(left == -1) { res.push_back(-1); return res; } int right = search(nums, target, false); res.push_back(right); return res; }