← Back to all posts
competitive-programmingDec 29, 20211 min read

[LeetCode] 34. Find First and Last Position of Element in Sorted Array Explained

Updated: Dec 28, 2021

Binary search
Available in:enko

#Problem

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

#Approach

For the first occurrence, a plain Binary Search does the job as-is.

Running binary search for the element 88 on the array [5,7,7,8,8,10][ 5, 7, 7, 8, 8, 10 ] yields 33.
Tracing through the code flow yourself makes it clear.

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

For the last occurrence, we can find it by binary searching for the value target+1 and then decrementing the index by one.

Only when target==nums[l]target == nums[l] is index ll itself the last occurrence, as an exception.

#Code

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

#Complexity

  • Time: O(log⁡n)O(\log n)
  • Space: O(1)O(1)