(๑>◡<๑)ノ
嗨，我是wec，今天是DAY 8。

🔎 題目難度與描述

難度：MEDIUM

題目描述：

有一個排序過的數組被從某個位置旋轉了，比如[4,5,6,7,0,1,2]。現在要在這個數組中找到一個目標數字，並返回它的索引。如果找不到，則返回-1，並用二分法解題。

🔎 解題思路＆程式碼

1️⃣ 迭代法

第1步： 從數組的兩邊開始，設定左邊(left)和右邊(right)的索引，代表我們要找的範圍。
第2步： 每次查找範圍的中間數字(mid)，看它是不是我們要找的目標數字。
第3步： 如果左邊那部分是排好序的，那就看看目標數字是不是在這個區間。如果不是，就去右邊那部分查找。(用這個方法將左右往中間篩選，縮小範圍)
第4步： 如果mid剛好是目標數字，直接返回它的索引。如果left和right最後重合了還沒找到，那就返回-1，表示目標數字不在數組裡。
程式碼：

def search(nums, target)
  left, right = 0, nums.length - 1

  while left <= right
    mid = (left + right) / 2
    return mid if nums[mid] == target

    if nums[left] <= nums[mid]
      target.between?(nums[left], nums[mid]) ? right = mid - 1 : left = mid + 1
    else
      target.between?(nums[mid], nums[right]) ? left = mid + 1 : right = mid - 1
    end
  end

  -1
end

🔎 總結

空間複雜度

二分法： 空間複雜度為O(1)
➡️ 因為二分法只使用了三個變數left、right與mid，來進行計算，沒有額外使用數組或其他結構，所以在空間的使用度上達到了常數級別，而且與輸入的資料大小無關。因為這題就規定時間複雜度必須為O(log n)，所以就計算一下空間複雜度嚕٩(๑•̀ω•́๑)و！

好的，那麽以上就是今天的中級路跑第一站啦～

相信IT人動腦時都要吃點東西，所以今天邊寫邊吃我自己煎的櫛瓜（很好吃）。
明天要說：Ruby精選刷題！Medium路跑D-2(>∀･)⌒☆