33. Search in Rotated Sorted Array

정렬된 정수 배열이 주어지고, 이 배열이 한 번 회전된 상태에서 특정 정수 값을 찾는 것입니다. 주어진 배열은 오름차순으로 정렬되어 있으며, 배열의 요소들은 고유합니다.

 

문제 설명

1. 입력 배열: 정수 배열 nums가 주어지며, 이 배열은 오름차순으로 정렬되어 있습니다.
2. 회전: 배열은 한 번 회전될 수 있습니다. 예를 들어, 배열 [0, 1, 2, 4, 5, 6, 7]이 주어질 때, 이 배열이 회전되어 [4, 5, 6, 7, 0, 1, 2]가 될 수 있습니다. 회전 인덱스 k는 1 이상이고 배열의 길이보다 작습니다.
3. 목표: 주어진 배열에서 특정 정수 target의 인덱스를 찾는 것입니다. 만약 target이 배열에 없다면 -1을 반환합니다.
4. 시간 복잡도: O(log n) 시간 복잡도로 알고리즘을 구현해야 합니다.

예시

• 예시 1:
  • 입력: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
  • 출력: 4 (0의 인덱스)
• 예시 2:
  • 입력: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
  • 출력: -1 (3은 배열에 없음)
  •  

 

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, 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;
	}
   }

이진 탐색을 통한 접근

1. 초기화: left와 right 포인터를 배열의 처음과 끝으로 초기화합니다.
2. 중간값 계산: mid 인덱스를 계산합니다.
3. 타겟 값 비교: nums[mid]가 target과 같은지 확인합니다. 같으면 mid를 반환합니다.
4. 정렬된 부분 확인: 배열의 왼쪽 절반이 정렬되었는지 확인합니다.
   • 왼쪽 절반이 정렬된 경우: target이 왼쪽 절반에 있는지 확인하여 left와 right를 조정합니다.
   • 오른쪽 절반이 정렬된 경우: target이 오른쪽 절반에 있는지 확인하여 left와 right를 조정합니다.
5. 반복: 위 과정을 left가 right보다 작거나 같을 때까지 반복합니다.
6. 결과 반환: 타겟 값을 찾지 못하면 -1을 반환합니다.