C++LeetCode 구현(81.회전 질서 배열 에서 검색 하 는 2)

[LeetCode]81.Search in Rotated Sorted Array II 회전 질서 배열 에서 검색
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:

This is a follow up problem to  Search in Rotated Sorted Array , where nums may contain duplicates.

Would this affect the run-time complexity? How and why?

이것 은 이전의 저것 이다  Search in Rotated Sorted Array  의 연장,현재 배열 에서 중복 숫자 가 나타 날 수 있 습 니 다.이것 은 우리 가 어느 쪽 을 선택 하여 계속 검색 하 는 지 에 영향 을 줄 수 있 습 니 다.예전 에 그 문 제 는 같은 값 이 존재 하지 않 았 기 때문에 우 리 는 중간 값 과 가장 오른쪽 값 을 비교 할 때 전에 말 한 규칙 에 완전히 부합 합 니 다.만약 에 중간 수량 이 가장 오른쪽 보다 적 으 면 오른쪽 부분 은 질서 가 있 습 니 다.만약 에 중간 수량 이 가장 오른쪽 수 보다 크 면왼쪽 부분 은 질서 가 있다.만약 에 중복 값 이 있 으 면 면 두 가지 상황 이 발생 한다.[3,1]과[1,3,1]이 두 가지 상황 에 대해 중간 값 이 가장 오른쪽 값 과 같 을 때 목표 값 3 은 왼쪽 에 있 을 수도 있 고 오른쪽 에 있 을 수도 있다.그러면 어떻게 해 야 하 는가?이런 상황 에 대해 사실은 처리 가 매우 간단 하 다.가장 오른쪽 값 을 왼쪽으로 한 자리 만 돌리 면 계속 순환 할 수 있 고 똑 같 으 면 계속 이동 할 수 있다.다른 값 으로 옮 길 때 까지 다른 부분 은 사용 합 니 다.  Search in Rotated Sorted Array  중의 방법 은 다음 과 같은 코드 를 얻 을 수 있 습 니 다.

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n = nums.size(), left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] < nums[right]) {
                if (nums[mid] < target && nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else if (nums[mid] > nums[right]){
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            } else --right;
        }
        return false;
    }
};

C++구현 LeetCode(81.회전 질서 배열 에서 검색 하 는 2)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++는 회전 질서 배열 에서 검색 하 는 2 내용 을 실현 합 니 다.이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 도 많은 응원 부탁드립니다!