42. Find Minimum in Rotated Sorted Array

読了目安約1分

Binary Search / LeetCode 153 (Medium) — 回転したソート済み配列の最小値を二分探索で求める。

この章の目次

問題

LeetCode 153. Find Minimum in Rotated Sorted Array（Medium / カテゴリ: Binary Search）

昇順の配列を何回か回転（先頭の要素を末尾へ移動）したものが与えられます。要素は相異なります。最小値を O(log n) で返してください。

考え方

ヒント 1

最小値は「回転の継ぎ目」にあります。 nums[mid] を区間の端の値と比べると、継ぎ目が mid の左右どちらにあるか分かります。

ヒント 2

nums[mid] > nums[high] なら、継ぎ目は mid より右にあるので low = mid + 1。そうでなければ最小値は mid 以下の範囲にあるので high = mid。 low == high になったら nums[low] が答えです。

Swift 実装のポイント

比較相手は nums[high] にします。nums[low] と比べると、回転していない（すでに昇順の）入力で誤った側に絞ってしまいます。
low = mid + 1（mid は最小値でないと確定）と high = mid（mid が最小値の候補として残る）の非対称に注意します。
ループ条件は low < high です。要素 1 個になったら止まります。

模範解答

Swift
class Solution {
    func findMin(_ nums: [Int]) -> Int {
        var low = 0
        var high = nums.count - 1
        while low < high {
            let mid = (low + high) / 2
            if nums[mid] > nums[high] {
                low = mid + 1
            } else {
                high = mid
            }
        }
        return nums[low]
    }
}

計算量: O(log n)。