<Medium> Search in Rotated Sorted Array (LeetCode : C#)

https://leetcode.com/problems/search-in-rotated-sorted-array/

📕 문제 설명

중복 없는 오름차순으로 정렬된 정수 배열이 주어질 때, pivot index k (1 <= k < nums.Length)를 기준으로 회전이 가능하다. 회전 후 결과는 nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1] 형태 이다. 회전 후의 정수 배열 nums와 target으로 주어진 값의 index를 반환하기

• Input
  회전된 정수 배열 nums, target 값
• Output
  target의 index (nums에 없으면 -1)

제한 => 시간 복잡도 : O (log n)

예제

풀이

이진 탐색에서 회전된 부분 고려해서 조건 추가하였다.

pivot 기준으로 이진 탐색 중간 값이 target 보다 클 때에 대해 4가지 부등호가 나올 수 있다. 그 중 일부 예를 그림으로 표현했는데 결국 제일 첫 케이스 빼고 나머지는 right 인덱스를 가져와야 함을 알 수 있다. 따라서 한 케이스에 대해 분기 처리를 했다.

mid 값이 target 보다 작은 경우도 비슷한 방식으로 확인해보면 nums[right] < target && nums[right] > nums[mid] 케이스에서만 오른쪽을 땡겨야 한다.

+) 중간에 테스트 케이스 하나가 걸려서 nums[left] < nums[mid]에 = 붙여주니 통과되었다.

nums = [3, 1] , target = 1

public class Solution {
    public int Search(int[] nums, int target) {

        int left = 0;
        int right = nums.Count() - 1;

        while (left <= right)
        {
            int mid = (left + right) / 2;
            
            if (nums[mid] == target) return mid;
            else if (nums[mid] > target) // target 보다 큰 값인 경우
            {
            	// left 땡겨야 하는 케이스
                if (nums[left] > target && nums[left] <= nums[mid]) left = mid + 1;
                else right = mid - 1;
            }
            else // target 보다 작은 값인 경우
            {
            	// right 땡겨야 하는 케이스
                if (nums[right] < target && nums[right] > nums[mid]) right = mid - 1;
                else left = mid + 1;
            } 
        }

        return -1;
        
    }
}

결과