43. Search in Rotated Sorted Array

読了目安約1分

Binary Search / LeetCode 33 (Medium) — 回転したソート済み配列から target の位置を二分探索で探す。

この章の目次

問題

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

昇順の配列を回転したものと、整数 target が与えられます。要素は相異なります。 target の位置を返し、存在しなければ -1 を返します。 O(log n) が要求されます。

考え方

ヒント 1

mid で 2 つに割ると、左半分と右半分の少なくとも一方は必ず昇順のままです。回転の継ぎ目が入るのは片側だけだからです。

ヒント 2

昇順の側は、端の値との比較だけで「target を含むか」を判定できます。含むならその側へ、含まないなら反対側へ範囲を絞ります。これで毎回範囲が半分になります。

Swift 実装のポイント

左側が昇順かどうかは nums[low] <= nums[mid] で判定します。< にすると、区間の要素が 1 個のときに判定を誤ります。
範囲の判定は nums[low] <= target && target < nums[mid] のように半開区間で書くと迷いません。
nums[mid] == target の判定を最初に置くと、残りは範囲を絞る処理だけになります。

模範解答

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

計算量: O(log n)。