Problem
Key Idea
์ฒซ ๋ฒ์งธ ์ถํ์ ๊ทธ๋ฅ Binary Search ๊ทธ๋๋ก๋ฅผ ํด์ฃผ๋ฉด ๋๋ค.
๋ฐฐ์ด \([ 5, 7, 7, 8, 8, 10 ]\) ์์ ์์ \(8\)์ ์ด์งํ์ํ๋ฉด ๊ฒฐ๊ณผ๋ \(3\)์ด ๋์จ๋ค.
์ฝ๋ ํ๋ฆ์ ํ๋ฒ ์ง์ ๋ฐ๋ผ๊ฐ๋ณด๋ฉด ์ดํด๊ฐ ๋๋ค.
const vector<int> nums = {5, 7, 7, 8, 8, 10};
const int target= 8;
int l= 0, r= n-1;
while (l < r) {
int m= l+(r-l)/2;
if (nums[m] < target) l= m+1;
else r= m;
}
// l == 3
๋ง์ง๋ง ์ถํ์ target+1 ๊ฐ์ ๋ํด ์ด์ง ํ์์ ํ๊ณ , ์ธ๋ฑ์ค๋ฅผ ํ๋ ์ค์ฌ์ฃผ๋ฉด ์ฐพ์ ์ ์๋ค.
\(target == nums[l]\)์ธ ๊ฒฝ์ฐ๋ง ์์ธ์ ์ผ๋ก ์ธ๋ฑ์ค \(l\)์ด ๋ง์ง๋ง ์ถํ์ด ๋๋ค.
Implementation
/**
* written: 2021. 12. 29. Wed. 00:15:07 [UTC+9]
* jooncco์ mac์์.
**/
typedef vector<int> vi;
class Solution {
public:
vi searchRange(vi &nums, int target) {
int n= nums.size();
if (n == 0) return vi(2,-1);
if (n == 1) return target == nums[0] ? vi(2,0) : vi(2,-1);
// ์ฒซ๋ฒ์งธ ์ธ๋ฑ์ค
// ๋ณดํต์ ์ด์งํ์์ ์ฒซ ๋ฒ์งธ ์ถํ์ ์ฐพ๊ฒ ๋๋ค. (integer division ํน์ฑ ๋๋ฌธ์)
int l= 0, r= n-1;
while (l < r) {
int m= l+(r-l)/2;
if (nums[m] < target) l= m+1;
else r= m;
}
if (nums[l] != target) return vi(2,-1); // ์กด์ฌํ์ง ์๋ ๊ฒฝ์ฐ
int firstIdx= l;
// ๋ง์ง๋ง ์ธ๋ฑ์ค
// {target+1}์ ํ์ํด์ l-1.
// ์์ธ case: target๋ณด๋ค ํฐ ๊ฐ์ด ์๋ ๊ฒฝ์ฐ l ์์ฒด๊ฐ ๋ง์ง๋ง ์ธ๋ฑ์ค๊ฐ ๋จ.
l= 0, r= n-1;
while (l < r) {
int m= l+(r-l)/2;
if (nums[m] < target+1) l= m+1;
else r= m;
}
int lastIdx= nums[l] == target ? l : l-1;
return {firstIdx, lastIdx};
}
};
- Time: \(O(\log n)\)
Leave a comment