[LeetCode/Top Interview 150] [Binary Search] 33. Search in Rotated Sorted Array

문제 링크: https://leetcode.com/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10^4 <= target <= 10^4

전략:

오름차순으로 정렬된 배열이 랜덤한 오프셋 k(주어지지 않음)만큼 회전한 채로 주어진다.
주어진 배열 안에 타겟넘버가 존재한다면 해당 인덱스를, 없다면 -1을 리턴하면 된다.
시간 복잡도는 O(log n)이하여야 한다.

이진탐색을 하며 중간값과 구간의 시작 위치 값을 비교해 오름차순인지 아닌지 체크하고, 그에 따라 2가지 로직으로 나눠서 다음 구역을 정하자.

코드 구현:

class Solution {
    public int search(int[] nums, int target) {
        int start = 0, end = nums.length-1;
        while (start < end) {
            int mid = (start+end) / 2;
            // 중간값이 타겟이면 즉시 리턴
            if (nums[mid] == target) { return mid; }
             // 오름차순
            if (nums[start]<=nums[mid]) {
                // 타겟이 시작위치 이상이고, 중간값보다 작은 경우
                // -> 타겟이 왼쪽 구간에 있을 수 있는 경우
                if (target >= nums[start] && target < nums[mid]) {
                    end = mid-1; // 왼쪽구간 탐색
                } else {
                    start = mid+1;
                }
            // 회전된 배열
            } else {
                // 타겟이 우측 값과 중간 값보다 작은 경우
                // -> 타겟이 오른쪽 구간에 있을 수 있는 경우
                if (target <= nums[end] && nums[mid] < target) {
                    start = mid+1;
                } else {
                    end = mid-1;
                }
            }
        }

        // While 문 탈출 이후라면 범위는 1개
        // 마지막 요소가 타겟이면 리턴
        if (nums[start] == target) {
            return start;
        } else {
            // -1 리턴
            return -1;
        }
    }
}
Time: 0 ms (100%), Space: 40.47MB (95.43%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0033-search-in-rotated-sorted-array/0033-search-in-rotated-sorted-array.java

Solutions 탭의 타인 코드:

public class Solution {
    public int search(int[] A, int target) {
        int lo = 0;
        int hi = A.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (A[mid] == target) return mid;
            
            if (A[lo] <= A[mid]) {
                if (target >= A[lo] && target < A[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > A[mid] && target <= A[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return A[lo] == target ? lo : -1;
    }
}
Time: 0 ms (100%), Space: 41.3 MB (52.07%) - LeetHub

회고:

그래도 역시 이진탐색은 정렬된 배열에 하는 게 더 상쾌하고, 이해가 잘 되는 해법인 거 같다.
비록 생각하는데 꽤 시간이 걸렸지만 정렬되지 않은 부분을 나눌 때 고민하며 if-else부분을 조금 더 잘 쓰게 된 것 같다.