[ LeetCode | Java ] 33. Search in Rotated Sorted Array 🛠️

dokim·2023년 9월 4일

[LeetCode] Top 150 leetcode

[LeetCode] Top Interview 150

목록 보기

39/51

🏷️33. Search in Rotated Sorted Array

1. 문제 설명

다음은 오름차순으로 정렬된 정수 배열 nums가 있습니다(중복되는 값이 없음).
함수에 전달되기 전에 nums는 알 수 없는 피벗 인덱스 k (1 <= k < nums.length)에서 회전될 수 있습니다. 이로 인해 결과 배열은 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0부터 시작)이 될 수 있습니다. 예를 들어, [0,1,2,4,5,6,7]는 피벗 인덱스 3에서 회전되어 [4,5,6,7,0,1,2]가 될 수 있습니다.
가능한 회전 후의 배열 nums와 정수 target이 주어졌을 때, target이 nums에 있다면 해당 인덱스를 반환하고, nums에 없다면 -1을 반환합니다.
O(log n)의 실행 시간 복잡도를 가진 알고리즘을 작성해야 합니다.

2. 접근 방법

3. 구현 코드

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

        while (l <= r) {
          int m = (l + r) / 2;
          if (nums[m] == target)
            return m;
          if (nums[l] <= nums[m]) {
            if (nums[l] <= target && target < nums[m])
              r = m - 1;
            else
              l = m + 1;
          } else {
            if (nums[m] < target && target <= nums[r])
              l = m + 1;
            else
              r = m - 1;
          }
        }

        return -1;
    }
}