153. Find Minimum in Rotated Sorted Array
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
풀이
오름차순으로 주어진 정수 배열의 몇번의 회전한다. 이 배열에서 최소 값을 찾아야한다.
정렬해서 맨 앞의 값 가져오면 단순한 문제지만 이 문제에서 O(log n)의 속도 내에서 탐색을하여 값을 가지고 와야한다.
이진탐색을해서 값을 가져오는게 맞는거 같은데, 음.. 배열이 [2,3,4,0,1] 일때 mid가 가장 큰 값이되고 양쪽값 모두 적은값이 된다, 이런 경우 어떻게 탐색을 진행해야할지 생각을 해봤다, 일단, 최초의 배열은 오름차순으로 정렬되어 있기 때문에 기본적으로 오른쪽으로 이동 할 수록 값이 증가하게된다.
1.양쪽 다 mid 값보다 작을 경우 ,둘 다 작다면 , mid는 배열의 값 중 회전되어서 잘려진 값이 양쪽으로 나누어져 있다는 것을 알 수 있다. 그렇다면 왼쪽으로 탐색해서 제일 작은 값을 찾아야한다.
2. 양 쪽다 mid값보다 클 경우 , 오른쪽으로 포인터를 이동하면서 찾아줘야한다, 기본적으로 오름차순인데, 오른쪽 값이 작다는 것은 회전해서 잘린 배열의 시작부분이 오른쪽에 있다는 걸 알 수 있다 ex)[3,4,0,1,2]
3. 최초에 배열의 양쪽 끝의 값을 먼저 확인해주고 , 만일 마지막 인덱스의 값이 0번 인덱스 값보다 작다면 회전하지않은 오름차순 그대로의 배열인걸 알 수 있다. [0,1,2,3,4]
4. right의 인덱스포인터를 통해 mid포인터를 움직여준다.
class Solution(object):
def findMin(self, nums):
if len(nums)<1:
return 0
left =0
right = len(nums)-1
if nums[left]<nums[right]: #맨 오른쪽값이 맨 왼쪽값보다 크다면 정렬된 배열인 걸 확인 가능
return nums[left]
while left<right-1: # 왼쪽 포인터가 오른쪽 포인터를 넘는다면 모든 탐색 완료,
if nums[mid] > nums[right]: #mid인덱스의 값이 right보다 크다면,
left = mid + 1 #왼쪽 포인터 = mid+1 (mid포인터의 위치와 오른쪽포인터 사이에 존재함)
else:
right = mid # 오른쪽 포인터 = mid (mid포인터의 위치와 왼쪽 포인터 사이에 존재함)
return nums[left]로직을 만들면서 잘 안풀려서 leetcode에서 다른사람의 코드를 보고 다시 만들었다.
그러면서 알게된건 내가 이진탐색에 대해서 좀 잘못이해하고있는걸 알게되었는데,
문제에서 주어지는 배열은 기본적으로 오름차순 정렬이라, right포인터를 통해 현재 인덱스의 상황을 알 수 있다.
mid의 값이 right보다 크다면 최소 값은 mid와 right에 존재하게되고, 만일 작다면 최소 값은 left와 mid 사이에에 존재하게된다, 이걸 생각못하고, right = mid-1을 사용해서 자꾸 찾아야되는 인덱스를 벗어나게되어서 문제가 생겼었다.
몇 일 뒤에 다시 풀어봐야겠다.