LeetCode 33. Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

 

 

풀이

 

오름차순 배열을 임의로 회전하여 target값의 인덱스를 찾아서 반환하는 문제이다.

 

사실 단순하게, for문이나 find함수를 통해서 값을 찾아올 수 있으나 문제에서 O(log n)의 시간복잡도를 원하므로 

 

O(log n)시간 복잡도로 탐색 할 수 있는 이진 탐색을 사용하겠다.

 

이진탐색을 통해서 left  right의 포인터 중간 미드 값을 기준으로 증가하는 방향과 감소하는 방향을 확인한 후

추가로  target값을 기준으로 mid 포인터를 움직여주면된다,

 

기본적으로 문제에서 오름차순으로 정렬된 리스트를 회전시켰기 때문에, 현재 배열의 상태가 right와 left를 mid값을 기준으로 크고 작음을 확인 한 뒤, 그 범위안에 target의 값이 존재하는지 확인하면 된다,

 

left < = target < mid   = left와 mid 사이에 target값이 존재

 

 mid< taget <= right 이라면 mid와 right아이에 값이 존재

 

이를 기반으로 이진탐색을 진행한다 .

 

class Solution(object):
    def search(self, nums, target):
        result = -1 
        left =0
        right = len(nums)-1
        while left<right:
            mid = (left+right)//2
            if nums[mid] == target:
                return mid
            if nums[left]<=nums[mid]:
                if nums[left] <= target and target < nums[mid]:
                    right = mid-1
                else:
                    left = mid+1
            else:
                if nums[mid] <target and target <= nums[right]:
                    left = mid+1
                else:
                    right= mid-1 
        return result