LeetCode 刷題日記
EP.07

Binary Search
每次砍掉一半，O(log n) 的魔法

#704 Binary Search · #33 Search in Rotated Sorted Array

Joseph Chen
October 2024
Back to Blog
5 min read
1.2k views

Binary Search 的概念每個人都懂——在排序好的陣列裡，每次比較中間的元素，再根據大小丟掉左半或右半，重複直到找到目標。但實際寫出來時，off-by-one error 讓很多人翻車。這篇先把基礎打穩，再看 Rotated Sorted Array 這個變形題。

為什麼是 O(log n)？

每一步都把搜尋範圍砍半。從 n 個元素開始，最多幾步才到 1 個？

步數剩餘元素n=1024 時
0n1024
1n/2512
2n/4256
3n/8128
.........
1011 ✅

1024 個元素最多只需要 10 步（log₂ 1024 = 10）。如果是 10 億個元素，也只需要 30 步。這就是 O(log n) 的威力。

#704 基本解法

Input / Output
Input:  nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4   ← nums[4] = 9

Input:  nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1  ← 不存在
Binary Search — 你的解法
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (right - left) // 2 + left   # 防止 overflow
            num = nums[mid]

            if num == target:
                return mid
            elif num < target:
                left = mid + 1    # 目標在右半，丟棄左半
            else:
                right = mid - 1   # 目標在左半，丟棄右半

        return -1
⏱ Time: O(log n)💾 Space: O(1)

mid = (right - left) // 2 + left 為什麼不直接寫 (left + right) // 2？

這是你程式碼裡的一個細節，值得單獨說明。

Integer Overflow 問題
為何不用 (left + right) // 2
# 在 C / Java / C++ 這類語言：
# int 的最大值是 2,147,483,647（約 2.1 億）
# 如果 left = 1,000,000,000, right = 2,000,000,000
# left + right = 3,000,000,000 → 超過 int 最大值 → overflow！

# 安全寫法：
mid = left + (right - left) // 2
# 等同於：
mid = (right - left) // 2 + left

# Python 的 int 沒有 overflow 問題（任意精度整數）
# 但這是面試標準寫法，養成習慣很重要

Python 的整數沒有 overflow，所以兩種寫法結果一樣。但這是面試的標準寫法，Java/C++ 面試時寫錯會被扣分。

Off-by-one：最常見的 Binary Search Bug

Binary Search 有兩種終止條件，容易搞混：

while left <= right

搜尋範圍包含 left == right 的情況（只剩一個元素還要檢查）。找「精確值」用這個。

left=3, right=3 → 還會進 loop
left=4, right=3 → 停止

while left < right

搜尋範圍不包含 left == right。找「邊界」（第一個 ≥ target 的位置）用這個。

left=3, right=3 → 直接停止
回傳 left 作為答案
逐步追蹤：nums=[-1,0,3,5,9,12], target=9
left=0, right=5 → mid=2, nums[2]=3 < 9 → left=3
left=3, right=5 → mid=4, nums[4]=9 == 9 → return 4 ✅

變形題：#33 Search in Rotated Sorted Array

如果陣列被「旋轉」過呢？

Input / Output
# 原本：[0, 1, 2, 4, 5, 6, 7]
# 旋轉：[4, 5, 6, 7, 0, 1, 2]  ← 從 index 4 切開並旋轉

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4

Input:  nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1

直接用 Binary Search 行不行？不行——旋轉後整個陣列已經不是單調遞增了，mid 的大小無法直接告訴你目標在左還是右。

關鍵觀察：旋轉後，陣列的左半和右半，其中一邊一定是有序的。 利用這個性質，先判斷哪一半有序，再決定要往哪邊走。

Search in Rotated Sorted Array
class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (right - left) // 2 + left

            if nums[mid] == target:
                return mid

            # 判斷左半是否有序
            if nums[left] <= nums[mid]:
                # 左半有序，且 target 在左半範圍內
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                # 右半有序，且 target 在右半範圍內
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1
⏱ Time: O(log n)💾 Space: O(1)

思維步驟

1.nums[mid] == target → 直接回傳
2.nums[left] <= nums[mid] → 左半有序
3.→ target 在左半範圍內 → right = mid - 1
4.→ 否則去右半 → left = mid + 1
5.nums[left] > nums[mid] → 右半有序
6.→ target 在右半範圍內 → left = mid + 1
7.→ 否則去左半 → right = mid - 1

Binary Search 的所有變形題，核心都是同一件事：在每一步，確保你能丟掉「目標一定不在那裡」的那一半。條件怎麼寫，取決於你能做出什麼保證。

本篇重點整理

✂️每次砍掉一半 → O(log n)，10 億個元素只需 30 步
🔢mid = left + (right - left) // 2，防 overflow 的面試標準寫法
⚠️while left <= right 找精確值；while left < right 找邊界
🔄Rotated Array：先判斷哪一半有序，再決定往哪邊走

上一篇

EP.06 — Stack

Valid Parentheses 與單調棧

下一篇

EP.08 — Linked List

Pointer 操作與 Dummy Node

LeetCode
Binary Search
Array
Python
EP.07