2 분 찾기 연습 - leetcode 34. 정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다.

leetcode 34. 정렬 배열 에서 요소 의 첫 번 째 와 마지막 위 치 를 찾 습 니 다.
오름차 순 으로 배 열 된 정수 배열 nums 와 목표 값 target 을 지정 합 니 다.주어진 목표 값 이 배열 의 시작 위치 와 끝 위 치 를 찾 습 니 다.
당신 의 알고리즘 시간 복잡 도 는 반드시 O (log n) 등급 이 어야 합 니 다.
배열 에 목표 치가 존재 하지 않 으 면 [- 1, - 1] 을 되 돌려 줍 니 다.
예시 1:
입력: nums = [5, 7, 7, 8, 8, 10], target = 8 출력: [3, 4] 예시 2:
입력: nums = [5, 7, 7, 8, 8, 10], target = 6 출력: [- 1, - 1]
코드

class Solution {
public:
    int FindLeftBoundary(vector&nums,int target){
        /*              */
        int left=0;
        int right=nums.size();
        while(lefttarget){
                right=mid;
            }
            else if(nums[mid]&nums,int target){
        /*           */
        int left=0;
        int right=nums.size();
        while(lefttarget){
                right=mid;
            }
            else if(nums[mid] searchRange(vector& nums, int target) {     
        int leftbound;
        int rightbound;
        leftbound=FindLeftBoundary(nums,target);
        rightbound=FindRightBoundary(nums,target);
        vector res={leftbound,rightbound};
        return res;
    }
};

분석 과 이해
2 분 검색 에 관 한 세부 설명 은 본 문 제 를 볼 수 있 는 labuladong 이 발표 한 '2 분 검색 알고리즘 세부 설명' 이라는 글 을 볼 수 있 습 니 다.이 안에서 작 가 는 2 분 검색 의 기본 템 플 릿 을 다음 과 같이 제시 했다. 그 중에서 작 가 는 else 를 else if () 로 써 조건 을 더욱 명확 하 게 하 는 것 을 강력 히 제안 했다.

//  ：labuladong
int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        int mid = (right + left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

또한 저 자 는 2 분 검색 을 3 가지 유형 으로 요약 했다. 하나의 요 소 를 찾 거나 왼쪽 경 계 를 찾 거나 오른쪽 경 계 를 찾 았 다.
나 자신 은 이렇게 몇 가지 이 해 를 가지 고 있다.
1. 왼쪽 경 계 를 찾 는 것 과 오른쪽 경 계 를 찾 는 기본 프레임 워 크 는 똑 같 습 니 다. 사용 하 는 구간 은 모두 [left, right) 이 고 초기 구간 은 [0, nums. size () 입 니 다. 따라서 순환 할 때 는 모두 left = = right 일 때, 즉 [left, left) 일 때 입 니 다.
2. 좌우 경계 찾기 는 경 계 를 압축 하 는 방향 이 다 르 기 때문에 압축 경 계 는 nums [mid] = = target 일 때 왼쪽 경 계 를 찾 으 면 오른쪽 경계 가 압축 되 기 때문에 right = mid 이 고 오른쪽 경 계 를 찾 으 면 왼쪽 경계 가 압축 되 기 때문에 left = mid + 1 이 고 나머지 nums [mid]! = target 일 때 경계 가 압축 되 는 상황 은 대체적으로 같다.
3. 왼쪽 경계 에서 찾 은 반환 은 다 릅 니 다. 왼쪽 경계 에서 찾 은 반환 은 left 로 되 돌아 갑 니 다. 오른쪽 경계 에서 되 돌아 오 는 것 이 라면 left - 1 (left = = right) 로 되 돌아 갑 니 다. 오른쪽 경계 에서 되 돌아 오 는 것 은 right - 1 이 라 고 쓸 수 있 습 니 다. 순환 할 때 left = = right 로 되 돌아 가기 때문에 특별한 상황 을 처리 해 야 합 니 다. 왼쪽 경계 에서 찾 습 니 다. nums 로 되 돌아 갑 니 다.[nums. size ()] 에 접근 할 수 없 으 므 로 left = = nums. size () 를 처리 해 야 합 니 다. 오른쪽 경계 찾기 는 nums [- 1] 에 접근 할 수 없 기 때문에 left = = 0 에 특 판 을 붙 여야 합 니 다. 왜 항상 left 와 관 계 를 맺 는 지, 아니면 왜 left = mid + 1, right = mid 이면 됩 니 다. 저 는 mid = (left + right) 에 있 기 를 원 합 니 다./ 2 시 에는 아래로 정 리 됩 니 다. 따라서 left 는 강제로 + 1 을 해 야 오른쪽으로 압축 할 수 있 습 니 다. 가장 간단 한 예 입 니 다.

left==0;
right==1;
mid==0;
left==mid==0;//     ，      

원 소 를 찾 을 수 없 는 상황 에서 생각 할 때 다음 에 표 시 된 원 소 는 무엇 입 니까?
왼쪽 경 계 를 찾 는 것 을 예 로 들 면 요 소 를 찾 을 수 없 으 면 최종 적 으로 돌아 오 는 것 이 left 이 고 돌아 오 는 결과 의 범 위 는 0, nums. size () 또는 중간 에 있 는 위치 입 니 다. 0 으로 돌아 오 면 특 판 을 통 해 target 이 모든 요소 보다 작 습 니 다. 예 를 들 어 num. size () 로 돌아 가 는 것 입 니 다.또한, target 이 모든 요소 보다 크다 는 것 을 특별히 설명 할 필요 가 없습니다. 또한 중간 위치 에 있 으 면 순환 하 는 과정 이 항상 left - target - right 로 계속 압축 되 고 압축 은 원 하 는 것 을 왼쪽으로 기울 이기 때문에 vector 에서 찾 아야 할 요소 가 존재 하지 않 을 때 마지막 단계 에 도달 하기 전에 반드시 다음 과 같은 관계 가 있 습 니 다.

nums[left]target;

마지막 단계 에서 절 차 를 시작 하기 전에 left = = right - 1 의 계산 결 과 는 mid = = left (정수 추출 로 인 한) 입 니 다. 이때 nums [mid] target 의 값 은 target 보다 첫 번 째 로 큰 숫자 입 니 다!
같은 이치 로 오른쪽 경 계 를 찾 으 려 면 마지막 단계 전에 left = right - 1, 마지막 계산 결 과 는 mid = = left 입 니 다. 이때 nums [mid]따라서 순환 을 뛰 어 넘 을 때 right 는 첫 번 째 target 보다 큰 수 를 가리 키 고 있 습 니 다. 왼쪽 경 계 를 취하 든 오른쪽 경 계 를 취하 든 left 의 업데이트 체 제 는 똑 같 기 때 문 입 니 다. 그러나 이때 우리 가 right - 1 로 돌아 가면 우리 가 얻 은 것 은 target 보다 작은 값 의 하 표 입 니 다.
이러한 세부 적 인 차이 에 대한 인과 논 리 를 정리 해 보 자.
첫 번 째, 가장 기본 적 인 이분 찾기 알고리즘:

Python
        right = nums.length - 1
        「    」  [left, right]
      while (left <= right)
       left = mid+1   right = mid-1

           target      
    nums[mid] == target        

두 번 째, 왼쪽 경계의 2 분 찾기:

Python
        right = nums.length
        「    」  [left, right)
      while (left < right)
       left = mid + 1   right = mid

        target       
    nums[mid] == target        
               

세 번 째, 오른쪽 경계의 2 분 찾기:

Python
        right = nums.length
        「    」  [left, right)
      while (left < right)
       left = mid + 1   right = mid

        target       
    nums[mid] == target        
               

             left = mid + 1
         left    right，