題目連結(https://leetcode.com/problems/binary-search/description/)

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

今天分享搜尋的經典題目，可延伸至許多應用問題，也要注意其與 Binary Search Tree 的比較

1. Repeat（題目重複確認）

• 輸入：一個已排序遞增的整數陣列 nums 和要搜尋目標數字 target。
• 輸出：存在則輸出 target 的 index，不存在則輸出 -1。
• 前提：執行時間複雜度要求在 O(log n)

2. Examples（舉例確認理解）

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4（9 的 index)

3. Approach（解題思路）

方法 1：線性搜尋

• 使用 for 迴圈依序遍歷 nums 陣列中的 n 個元素，如果找到目標值，返回該索引。
• 時間複雜度：O(n) 每個元素都要檢查，故為 O(n)
• 空間複雜度：O(1)

方法 2：二分搜尋

• 需要改進時間複雜度才能滿足題目要求，故使用devide and conquer(分治法），定義 private 函數，定出左右端點並找出中點，和目標值比較，用遞迴法實作較簡潔，不斷砍半搜尋範圍，遞迴搜尋左半或右半。（迭代法也可以寫）
• 時間複雜度：O(log n) 每次呼叫搜尋範圍都會減半：T(n) = T(n/2) +1, T(1) = 1
• 空間複雜度：O(1)

4. Code（C++）

#線性搜尋
class Solution {
public:
		int search(vector<int>& nums, int target) {
				for (int i = 0; i < nums.size(); i++) {
						if (nums[i] == target) {
							return i;  // 找到目標，返回索引
						}
				}
				return -1;  // 沒有找到目標，返回 -1
		}
};

#二分搜尋
class Solution {
public:
    int search(vector<int>& nums, int target) {
        return bs(nums, 0, nums.size() - 1, target);
    }

private:
    int bs(vector<int>& nums, int l, int r, int target){
        if(l > r)
            return -1;
        
        int m = l + (r-l)/2; //避免溢位

        if(nums[m] == target)
            return m;
        else if(nums[m] < target) //遞迴搜尋右半
            return bs(nums, m+1, r, target);
        else //遞迴搜尋左半
            return bs(nums, l, m-1, target);
    }
};

5. Test 範例

1. 執行 bs(nums, 0, 5, 9)

m = 2, nums[2] = 3 < 9, return bs(nums, 3, 5, 9)

2. 執行 bs(nums, 3, 5, 9)

m = 4, nums[4] = 9 = target, return 4 (9 的 index)

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

6. 相關題目與延伸概念

• 35. Search Insert Position
• 34. Find First and Last Position of Element in Sorted Array
• 69. Sqrt(x) 解數學題
• 進階：應用問題 1011. Capacity To Ship Packages Within D Days

7. 補充：語法＆注意事項

中間值 m = left +(right-left)/2 避免溢位

ps. 部分內容經 AI 協助整理