[Leetcode Top Interview 150] 33. Search in Rotated Sorted Array

난이도 : medium

문제링크

• 정수형 배열 nums이 주어진다
  • 오름차순으로 정렬되었으며 
  • 각 요소들은 유일하다
• k 번째 인덱스를 기준으로 회전될 수 있다
• target의 인덱스를 리턴하라
• O(logn)의 시간복잡도를 가지는 알고리즘으로 작성해야 한다

 

3. 구현 코드

public int search(int[] nums, int target) {
    if (nums.length == 1) {
        if (nums[0] == target) return 0;
        else return -1;
    }

    int length = nums.length;
    int left = 0, right = length-1;

    while (left <= right) {
        if (nums[left] == target) {
            return left;
        }

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

        left++;
        right--;
    }

    return -1;
}

 

6. 회고

• binary search로 구현하는것이 어려워 chatgpt에 물어보았다

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

        while (left <= right) {            
            int mid = (left+right)/2;
            if (nums[mid] == target) {
                return mid;
            }

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

        return -1;
    }
}

• 투포인터를 사용하고, 중간에 위치한 요소가 target인지 체크한다
• left ~ mid까지가 오름차순이라면
  • target이 left~mid 안에 존재한다면 -> right = mid -1;
  • target이 left~mid 안에 존재하지 않는다면 -> left = mid +1;
• left ~ mid까지가 오름차순이 아니라면
  • target이 mid ~right 안에 존재한다면 -> left = mid +1;
  • target이 mid ~right 안에 존재하지 않는다면 -> right = mid -1;