👀 문제
https://leetcode.com/problems/search-in-rotated-sorted-array/
👊 도전
1. 설계
- 이분탐색을 이용해 정렬된 구간이 어딘지 찾는다.
- 정렬된 구간에 target이 포함된다면 그곳으로, 아니라면 반대로 이동한다.
- mid로 target을 찾을 때 까지 반복한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
*
* @author HEESOO
*
*/
class Solution {
public int search(int[] nums, int target) {
int left=0, right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(target==nums[mid]) return mid;
if(nums[left]<=nums[mid]){ // 왼쪽 배열이 정렬되어 있다면
// 이 배열에 target이 존재한다면 그쪽으로 범위 좁힘
if(nums[left]<=target && target<nums[mid]) right=mid-1;
// 아니라면 반대쪽 배열로 범위 좁힘
else left=mid+1;
}
else{ // 오른쪽 배열이 정렬되어 있다면
if(nums[mid]<target && target<=nums[right]) left=mid+1;
else right=mid-1;
}
}
return -1;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 이분탐색을 이용한다
- 이분탐색은 배열이 오름차순으로 정렬되어있어야 가능하다.
- 문제에서는 특정 원소를 기준으로 회전하는데 그 원소가 무엇인지 알 수 없으므로, 이분 탐색으로 mid를 결정하고 mid 기준 왼쪽 오른쪽 중 정렬된 곳이 어디인지 체크한다.
- 해당 정렬된 곳에 target이 포함된다면 그곳으로 이동, 아니라면 반대로 이동하여 mid가 target이 될 때 까지 찾는다.