search

seungriyou / algorithm-study

알고리즘 & SQL 문제 풀이 기록
https://leetcode.com/u/summer_y
0 stars 0 forks source link

[LC] 33. Search in Rotated Sorted Array #35

Open seungriyou opened 8 months ago

seungriyou commented 8 months ago

https://leetcode.com/problems/search-in-rotated-sorted-array/

Approach

기본적으로 정렬되어 있는 배열이며, O(logn) time으로 동작해야 하므로 binary search로 접근한다.

오름차순으로 정렬된 배열이 rotate 되어 있으므로, mid의 원소뿐만 아니라 left 혹은 right의 원소와도 비교해야 한다. (나는 right와 비교)

left <= right 동안 동작하는 과정은 다음과 같다.

  1. nums[mid] == target이라면, mid를 반환한다.

  2. nums[mid] <= nums[right]라면, mid 기준 오른쪽(mid ~ right)이 정렬된 것이다.

    • 정렬된 오른쪽에 target이 위치한다면, left를 mid + 1로 변경한다.
    • 아니라면, right를 mid - 1로 변경한다.

  3. 아니라면, mid 기준 왼쪽(left ~ mid)이 정렬된 것이다.

    • 정렬된 왼쪽에 target이 위치한다면, right를 mid - 1로 변경한다.
    • 아니라면, left를 mid + 1로 변경한다.

만약, left <= right이 더이상 아니게 되면, target이 존재하지 않는다는 것이므로 -1을 반환한다.


Complexity