[Algorithm][Array] 문제 풀이 #8 - Search in Rotated Sorted Array II

문제 링크

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

 

내 코드

public boolean search(int[] nums, int target) {
    int left = 0;
    int right = nums.length -1;
    while(left <= right){
        int mid = left + (right - left) / 2 ;
        if(target == nums[mid]) return true;

        if(nums[left] == nums[mid]) {
            left++;
            continue;
        }

        if(nums[left] < nums[mid]) {
            if(target == nums[left]) return true;
            if(target < nums[mid] && target > nums[left])
                right = mid;
            else
                left = mid;
        } else if(nums[left] > nums[mid]) {
            if(target == nums[right]) return true;
            if(target > nums[mid] && target < nums[right])
                left = mid;
            else
                right = mid;

        }
    }

    return false;
}

결과

이게 뭐라고...

이진 트리 검색은 그래도 공식이 있어서 괜찮은것 같다.

위에 포스팅했던 글처럼 한개의 for문으로 돌려보니 통과는 했지만 속도가 나지 않아

예전에 퀵정렬 풀었던 문제를 참고하여 다시 짜봤다.

코테 보기전에 복습해야 할 문제 1순위....