# 【LeetCode刷題】【演算法學習筆記】 704. Binary Search
* 學習時間：2025/01/25（Sat.）- 1/27 (Mon.)
* **題目連結（美服）：**[704. Binary Search](https://leetcode.com/problems/binary-search/editorial/)
* **題目連結（國服）：** [704. 二分查找](https://leetcode.cn/problems/binary-search/description/)
* Reference: [代碼隨想錄](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0704.二分查找.md) [Neetcode](https://www.youtube.com/watch?v=s4DPM8ct1pI)

### A. 解題技術點
---
1. [陣列（Array）](https://hackmd.io/@oliver-jhih-cs/ryO4s7MdJe)
2. [二分搜尋法（Binary Search）](https://hackmd.io/@oliver-jhih-cs/rJI1aXz_yg)
3. [時間複雜度（Time Complexity）](https://medium.com/appworks-school/初學者學演算法-從時間複雜度認識常見演算法-一-b46fece65ba5)

### B. 題目
---
* 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.

### C. 題意（中文）
---
> 給定一個升序排序（從小到大排列）的整數陣列 nums，以及一個整數目標值 target，請你撰寫一個函式來在這個陣列中尋找目標值。

1. 如果 target 存在於陣列中，回傳它的索引值（**index**）。
2. 如果 target 不存在，回傳 **-1**。
3. 要求：演算法時間複雜度為 **O(log n)**

### D. 參考程式碼
---
:::spoiler Solution (題解)

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Initialize two pointers
        l, r = 0, len(nums) - 1

        # Binary search
        while l <= r:
            # Calculate the middle index
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid  # Found target
        
        return -1  # Target not found

:::

:::spoiler Note（筆記）
1. **Binary Search Basic**
* It works only on sorted (已排序的) arrays.
* The idea (方法) is divide (分割) the search range in half reapetedly (反覆).
2. **Logic Breakdown (邏輯分解)**
* Check the **middle value** (中間值) (**nums[mid]**)
* If it **matches** the target, return the ==index==.
* If it's **smaller**, the target must be in the right half, so mid move ==left==.
* If it's **larger**, the target must be in the left half, so mid move ==right==.

4. **Efficiency (效率)**
* Time complexity: **O(log n)** because the search range is halved (一半) at each step.
* Space complexity: **O(1)** Since no extra (額外的) space is used.