회전 정렬 배열 검색 II

오름차 순 으로 정렬 된 배열 이 미리 알 수 없 는 한 점 에서 회전 했다 고 가정 합 니 다.
(예 를 들 어 배열 [0,0,1,2,2,5,6] 은 [2,5,6,0,0,1,2] 로 변 할 수 있다.
주어진 목표 값 이 배열 에 존재 하 는 지 여 부 를 판단 하기 위해 함 수 를 만 듭 니 다.반환 true 이 존재 하지 않 으 면 반환 false 합 니 다.
예시 1:

  : nums = [2,5,6,0,0,1,2], target = 0
  : true

예시 2:

  : nums = [2,5,6,0,0,1,2], target = 3
  : false

제목 분석:
이 문 제 는 회전 정렬 배열 을 검색 하 는 확장 입 니 다. 그 차이 점 은 배열 의 요 소 를 반복 할 수 있 습 니 다. 결 과 는 target 이 배열 에 있 는 지 여 부 를 판단 하 는 것 입 니 다. target 이 배열 에 있 는 위 치 를 되 돌려 주 는 것 이 아 닙 니 다.
배열 의 요 소 를 중복 할 수 있 기 때문에 문제 가 발생 할 수 있 습 니 다. 배열 을 회전 할 때 회전 하 는 위 치 는 target 일 수 있 습 니 다. 즉, 여러 target 을 분리 하 는 것 입 니 다. 예 를 들 어 배열 [0,0,1,2,2,5,6] 은 [2,5,6,0,0,1,2] 로 변 할 수 있 고 target = 2. 이 럴 때 회전 정렬 배열 의 구분 방법 을 검색 하면 target > nums[mid] 또는 target < nums[mid]기준 으로 2 분 에 충돌 문제 가 발생 하기 때문에 여 기 는 nums[mid] > nums[left] 또는 nums[mid] < nums[left] 를 기준 으로 해 야 한다.
이 문제 의 도형 분석 은 검색 회전 정렬 배열 과 유사 하 다.
코드 구현:

public boolean search(int[] nums, int target)
{
   int left = 0;
   int right = nums.length - 1;

   while (left <= right)
   {
       int mid = left + (right - left) / 2;
       if (nums[left] == target || nums[mid] == target || nums[right] == target)
           return true;
       else if (nums[mid] > nums[left])
       {
           if (target > nums[mid])
               left = mid + 1;
           else
           {
               if (target > nums[left])
                   right = mid - 1;
               else
                   left = mid + 1;
           }
       }
       else if (nums[mid] < nums[left])
       {
           if (target < nums[mid])
               right = mid - 1;
           else
           {
               if (target > nums[left])
                   right = mid - 1;
               else
                   left = mid + 1;
           }
       }
       else
           left++;//         ，    ，              target
   }
   return false;
}

주 함수:

public static void main(String[] args)
{
   S2 s = new S2();
   System.out.println(s.search(new int[]{2, 5, 6, 0, 0, 1, 2}, 5));
   System.out.println(s.search(new int[]{1, 1, 3, 1}, 3));
   System.out.println(s.search(new int[]{1, 1, 3, 1}, 2));
}

실행 결과:
true true false