【Leetcode 筆記】704. Binary Search

題目解釋

給定一個按 ascending sorted 的整數 array nums 和一個整數 target，寫一個函數在 nums 中搜尋 target。

如果 target 存在，則傳回其 index。否則，回傳 -1。

您必須編寫一個在 O(log n) 時間內執行的演算法。

範例

• 輸入: nums = [-1, 0, 3, 5, 9, 12], target = 9
• 輸出: 4

目標 9 在 nums 的第 4 個位置。

最佳解法

看到 O(log n) 就要反射性的想到二元搜尋法 (Binary Search)！

雖然不是 Blind 75，
不過在寫 Binary Search 的相關題目時還是建議熟悉一下，
會省事很多～

程式碼

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while (left <= right):
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return mid
            elif target <= nums[mid]:
                right = mid - 1
            else:
                left = mid + 1

        return -1

時間複雜度

O(logn)，n 是 nums 的元素個數。

空間複雜度

O(1)。

結語

超高頻的基本題，不可不會！

我朋友說他面 NVIDIA 研替也考了這題，可惡，好羨慕 XD

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26