LeetCode 153. Find Minimum in Rotated Sorted Array

문제 링크

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

문제 해석

• 초기 배열은 정렬 상태
• 배열에서 x 번 회전 ( 1<= x<=n )
• nums 요소는 unique
• 시간복잡도는 O(logn) 준수
• 배열중 가장 최소값을 return

문제 해결

• half 변수를 만들어 한번 더 검증
• mid 값이 right 값보다 작을시
  - half 값이 mid 보다 크거나 같고 left 보다 작을시?

  => left = half+1

  => half 는 필요가 없다!
• 단순히 right index 값 보다 작으면?
  => right = mid -1

왜 가능한가?

무조건 회전을 1회 이상 해야하므로 , 최소값은 무조건 오른쪽 부분에 있음

슈도 코드

while left<=right:
	mid = (left+right)/2
    	if num[mid-1]>num[mid]
        	return mid
        if num[mid]<num[right]
        	right = mid -1
        else
        	left = mid +1
return mid

결과

사담

첫 번째 이진 검색 문제는 못 풀었으나 , 이번 문제는 좀 헤매더라도 풀었다.
회전되어 있는 이진 검색이라도 , 문제가 원하는 조건을 잘 파악해서,
기존과 같이 접목을 할 수 있다는 걸 깨달았다.
이진 검색은 경계 조건을 잘 정하고 , 테스트 케이스를 통해서 반례 값들을 제거해나가는 접근 방식도 괜찮은거 같다.

메모본