[Java] LeetCode 33번 Search in Rotated Sorted Array

[Java] LeetCode 33번 Search in Rotated Sorted Array

로테이션이 되어있으면 숫자를 오름차순의 구역 두개의 구역으로 나누어서 생각할 수 있다. 왼쪽의 첫번째가 무조건 첫번째의 숫자가 오른쪽 구역의 첫번째 숫자보다 크게된다. 이 지점을 binary search로 찾는다.

오른쪽 구역의 시작 점을 turnPoint라는 변수에 저장하였다. 이제 왼쪽과 오른쪽 구역에서 각각 일치하는 숫자의 index를 찾고 이것을 return 해주면 된다.

class Solution { public int search(int[] nums, int target) { int first = nums[0]; int n = nums.length; int l = 1; int r = n - 1; int turnPoint = 0; int answer = -1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] <= first) { turnPoint = mid; r = mid - 1; } else { l = mid + 1; } } l = turnPoint; r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] < target) { l = mid + 1; } else if (nums[mid] > target) { r = mid - 1; } else { answer = mid; break; } } l = 0; r = turnPoint - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] < target) { l = mid + 1; } else if (nums[mid] > target) { r = mid - 1; } else { answer = mid; break; } } return answer; } }

반응형

from http://blue-jay.tistory.com/82 by ccl(A) rewrite - 2021-10-02 04:27:57