목록 정렬

요구사항 정의

nums오름차순으로 정렬된 정수 배열이 있습니다 ( 고유한 값 포함).

함수에 전달되기 전에는 결과 배열이 ( 0-인덱스 ) 되도록 알 수 없는 피벗 인덱스 ( )에서 회전할 수nums 있습니다 . 예를 들어 피벗 인덱스에서 회전하여 가 될 수 있습니다 .k1 <= k < nums.length[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]][0,1,2,4,5,6,7]3[4,5,6,7,0,1,2]

nums 가능한 회전 후의 배열 과 정수가 주어 지면 에 있는 경우 또는 에 없는 경우 의 인덱스를target 반환합니다 .targetnums-1nums

O(log n)런타임 복잡성이 있는 알고리즘을 작성해야 합니다

풀이방법

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

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

           
            if (nums[left] <= nums[mid]) { 
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { 
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}