Find Minimum in Rotated Sorted Array

문제

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

입력

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000

결과

ans: Int = 배열의 최솟값

해석

정렬이 됐지만 회전까지 들어가 있어 문제의 본질을 파악하는데 함정을 파뒀다.

하지만 시간 복잡도 제약이 O(logn)인 것을 보고 이분 탐색이라는 것을 눈치 챌 수 있었다.

 

mid를 기준으로 right 값이 큰지 작은 지를 판단하여

크다면 오른쪽 부분은 버려주는 형식으로 진행

코드

class Solution {
    func findMin(_ nums: [Int]) -> Int {
        let n = nums.count

        if n ==  1{
            return nums[0]
        }

        var left = 0
        var right = n - 1

        var ans: Int = Int.max
        while left < right {
            let mid = (left+right) / 2

            if nums[mid] <= nums[right] {
                right = mid
            } else {
                left = mid + 1
            }
        }

        return nums[left]
    }
}

 

자주 쓰는 이분 탐색 코드

	하한 ( Lower Bound )	상한 (Upper Bound)
의미	주어진 값 이상인 첫 번째 위치	주어진 값보다 큰 첫 번째 위치
결과	>= (같거나 큰 값의 위치)	> (보다 큰 값의 위치)
특징	배열에서 특정 값이 존재하지 않더라도, 그 값보다 큰 첫 번째 위치를 반환	특정 값이 배열에 여러 개 존재하더라도 마지막 값 이후의 위치를 반환

 

 

func lowerBound(_ arr: [Int], _ x: Int) -> Int {
  var start = 0
  var end = arr.count-1
  
  while (start < end) {
    let mid = (start + end) / 2
    if arr[mid] >= x { end = mid }
    else { start = mid + 1}
  }

  return end
}

func upperBound(_ arr: [Int], _ x: Int) -> Int {
  var start = 0
  var end = arr.count-1
  
  while (start < end) {
    let mid = (start + end) / 2
    if arr[mid] > x { end = mid }
    else { start = mid + 1}
  }

  return end
}