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