정렬 된 배열 + 2 점 에서 요소 의 첫 번 째 및 마지막 위 치 를 찾 습 니 다.

제목 을 베 끼 기 가 귀 찮 습 니 다. 아마도: 오름차 배열 에서 정수 target 을 지정 하고 첫 번 째 와 마지막 target 의 색인 을 찾 아 {index 1, index 2} 을 되 돌려 줍 니 다. 그렇지 않 으 면 {- 1, - 1} 을 되 돌려 줍 니 다.
시간 복잡 도 요구: O (logn)
분석: 시간 을 맞 추고 찾 아야 합 니 다. 우 리 는 2 분 동안 찾 을 생각 을 하기 어렵 지 않 습 니 다.그런데 한 가 지 는 첫 번 째 와 마지막 을 어떻게 알 아 냈 을 까?이것 은 나 를 괴 롭 혔 다.
알고리즘: leetcode caikehe 에서 왔 습 니 다.
1. 이분 변 체 를 사용 하여 target 을 index 1 로 찾 고 target + 1 을 index 2 로 찾 습 니 다.
2. index 를 판단 합 니 다. 경 계 를 넘 지 않 고 대응 값 이 target 과 같 으 면 {index 1, index 2 - 1} 을 되 돌려 줍 니 다.그렇지 않 으 면 {- 1, - 1} 로 돌아 갑 니 다.
소스 코드

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //binary find
        int index1 = binarySearch(nums, target);
        int index2 = binarySearch(nums, target+1) - 1;
        if(index1 < nums.size() && nums[index1] == target)
            return {index1, index2};
        return {-1, -1};
    }
    //    
    int binarySearch(vector<int>& nums, int target)
    {
        int l = 0, r = nums.size()-1;
        while(l <= r)
        {
            int mid = l + (r-l)/2;
            if(nums[mid] < target)
                l = mid + 1;
            else
                r = mid -1;
        }
        return l;
    }
};

 이해 하기 쉬 운 알고리즘

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) {
 4         int len = nums.size();
 5         if(len <= 0)
 6             return {-1, -1};
 7         if(len == 1)
 8             if(nums[0] == target)
 9                 return {0, 0};
10             else
11                 return {-1, -1};
12             
13         
14         int l = 0, r = len-1, mid;
15         while(l <= r)
16         {
17             mid = l + (r-l)/2;
18             if(nums[mid] == target)
19                 break;
20             else if(nums[mid] > target)
21                 r = mid - 1;
22             else
23                 l = mid + 1;
24         }
25         if(nums[mid] != target)
26             return {-1, -1};
27         
28         l = mid, r = mid;
29         while(l >= 0 && nums[l] == nums[mid])
30             l--;
31         while(r < len && nums[r] == nums[mid])
32             r++;
33         return {l+1, r-1};
34     }
35 };