[LeetCode Top Interview 150] [Binary Search] 153. Find Minimum in Rotated Sorted Array
[LeetCode Top Interview 150]
[문제 링크]
[문제 설명]
오름차순으로 정렬된 길이의 배열이 회전 정렬된다고 가정한다.
예를 들어 nums = [0,1,2,4,5,6,7]
- [4,5,6,7,0,1,2] 4번 회전한 경우
- [0,1,2,4,5,6,7] 7번 회전한 경우
고유 요소 nums 배열의 정렬된 회전 배열이 주어지면, 배열의 최소 요소를 반환한다. 시간 복잡도는 O(logN)을 가진다.
Example 1
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.
[처음에 내가 생각해 본 방법]
이전에 풀었던 Peak 요소 찾기랑 비슷하다. 이진 탐색 알고리즘을 활용하여 푸는 문제이고, 162번 문제와 다른 점은 최소값을 찾아야한다는 것 정도? 저번 문제를 먼저 풀어서 상대적으로 덜 어려운 느낌이었다..! 대신 최소값 대신 회전을 몇 번 했는지 횟수를 구하거나 하는 다른 조건이 추가되었다면 더 어려웠을 것 같다. 어떤 원리일까 더 생각을 해봤는데 이진 탐색의 경우에는 배열의 중간값을 기준으로 예시 배열 중 [3,4,5,1,2] 같은 경우 [3,4,5][1,2]와 같이 부분 배열로 나뉘게 되는데 이땐 정렬이 되어있는 상태여서 조금 더 수월하게 최소값을 찾을 수 있는 것 같다..!
주어진 배열의 중간 값을 먼저 찾고, 먼저 중간값과 마지막값의 대소에 따라 점점 범위를 조정해나가는 식으로.. 살짝 다르지만 원리는 비슷하게 생각해보았다. 점점 범위가 좁혀져서 start == end의 값이 같아지는 경우, 그 때가 바로 찾아야하는 최솟값의 인덱스이므로 같으면 반복문이 종료된다.
[의사 코드]
//인덱스는 0부터 시작하므로
// (가장 왼쪽의 시작값과 가장 오른쪽의 마지막값 구하기)
시작값=0, 마지막=배열 길이-1;
while(시작값<마지막값)
//중간값 구하기
중간값 = 시작값 + (마지막값 - 시작값) / 2;
// 만약 현재 중간값이 마지막 값보다 작다면?
if 배열[중간] 인덱스 값 < 배열[마지막] 인덱스 값
마지막값=중간값;
else
시작값=중간값+1;
return 배열[시작값];[실제 구현 코드]
class Solution {
public int findMin(int[] nums) {
int start = 0, end = nums.length-1;
while(start < end){
int mid = start + (end - start) / 2;
if(nums[mid] < nums[end]){
end = mid;
}else {
start = mid+1;
}
}
return nums[start];
}
}nums = [3,4,5,1,2]
1) start = 0; end = 배열의 길이-1이니까 4
2) 0<4이므로 반복문 실행
3) mid = 2;
4) nums[2] = 5, nums[4]=2;
5) 5>2이므로, start = 3; (end = 4;)
6) 3<4이므로 반복문 실행
7) mid = 3;
8) nums[3] = 1, nums[4]=2;
9) 1<2이므로, end = 3;
10) stat =3 / end = 3으로 두 값이 같으므로 반복문 종료, 찾은 인덱스 3 값 return (배열의 3번째 값인 1 리턴);
[똑같이 고려해봐야 할 사항]
이번 문제도 비슷하게 중간 값을 구할 때 문제가 생길 수 있어서
(만약에 (start+end) 값이 int 값의 범위(-2,147,483,648 ~ 2,147,483,647)보다 크다면, 음수 값으로 오버플로우 되어 2로 나누면 mid 값이 최종적으로 음수가 되는 문제)
int mid = start + (end - start) / 2이와 같이 중간값을 구하도록 작성해보았다.
