[Java Script] 33. Search in Rotated Sorted Array

1. 문제 개요

문제 링크 : 33. Search in Rotated Sorted Array

Search in Rotated Sorted Array - LeetCode

 

• 정렬된 상태에서 일정수의 회전연산이 일어난 배열이 주어집니다. 해당 배열에서 타겟값이 존재할경우 해당 값의 인덱스를 리턴하고 없을경우 -1을 리턴하면 되는 문제입니다.
• 시간복잡도 조건을 일치시켜야합니다.

 

2. 문제 풀이

문제의 요점은 이진 탐색을 이용해야 하지만 회전때문에 정렬이 깨진 상태에서 어떻게 이진탐색을 사용하냐가 주 요소입니다. 하지만 회전연산이 이루어 졌다고 문제에서 주어졌기 때문에 결국 일정 위치 이상의 값에서는 정렬이 이루어집니다.

그렇기에 중간값에서 탐색을 이루어야할 위치값을 특정하는 것을 중요 포인트로 잡았습니다.

 

 

주석으로 구현할 구조를 짜보겠습니다

var findPeakElement = function(nums) {
	// 중간값 도출
    // 중간값과 시작값을 비교하여 탐색 시작점 구하기
    // 이진탐색 진행
};

 

 

LeetCode 요구 양식으로 코드 구현

var search = function(nums, target) {
    let low = 0, high = nums.length - 1;

    while (low <= high) {
        let mid = Math.floor((low + high) / 2);

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

        if (nums[low] <= nums[mid]) {
            if (nums[low] <= target && target < nums[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        } else {
            if (nums[mid] < target && target <= nums[high]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
    }

    return -1;
};

 

LeetCode 제출 결과

 

이렇게 구현에 성공하였습니다.

3. 시간 복잡도 계산

O(n) = O(n)

4. 개선 사항 및 어려웠던 점

이진 탐색의 기본조건인 정렬이 깨진 상태에서 이진탐색을 어떻게 사용해볼지 고민하여야 했던 문제입니다.

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.