109 年 國立臺灣大學生物機電系碩士班丙組《計算機概論（D）》

本題考查排序演算法中的選擇排序法 (Selection Sort)。

核心觀念：
選擇排序法是一種簡單直觀的排序演算法。它的基本思想是：每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部排序完成為止。

解題步驟：

1. 理解選擇排序法：

   • 在每一輪迭代中，從未排序的部分找到最小（或最大）的元素。
   • 將該元素與未排序部分的第一個元素交換位置。
   • 重複此過程，直到整個序列排序完成。

2. 執行選擇排序：
   原始列表： [17, 23, 14, 6, 8]

   Iteration 1:

   • 尋找未排序部分 ([17, 23, 14, 6, 8]) 的最小值。最小值是 6，位於索引 3。
   • 將最小值 6 與未排序部分的第一个元素 17 交換。
   • 列表變為： [6, 23, 14, 17, 8]
   • 比較次數： 4 (17 vs 23, 17 vs 14, 17 vs 6, 17 vs 8)
   • 交換次數： 1

   Iteration 2:

   • 尋找未排序部分 ([23, 14, 17, 8]) 的最小值。最小值是 8，位於索引 4 (原列表索引)。
   • 將最小值 8 與未排序部分的第一个元素 23 交換。
   • 列表變為： [6, 8, 14, 17, 23]
   • 比較次數： 3 (23 vs 14, 23 vs 17, 23 vs 8)
   • 交換次數： 1

   Iteration 3:

   • 尋找未排序部分 ([14, 17, 23]) 的最小值。最小值是 14，位於索引 2 (原列表索引)。
   • 最小值 14 已經在未排序部分的第一个位置，無需交換。
   • 列表保持： [6, 8, 14, 17, 23]

核心觀念

本題考查有號整數的二補數表示法與二進位加法。

對於使用 $n$ 位元的二補數：

• 可表示範圍為

• 正數直接以二進位表示，最高位為 $0$。
• 負數的二補數表示法：

題目中的最小值為 $-300$。由於：

所以 $10$ 位元的表示範圍為 $-512$ 至 $+511$，足以表示 $-300$ 與 $+254$。因此採用 $10$ 位元計算。

解題方法

1. 將 $+254$ 表示成十位元二進位

因此：

2. 將 $-300$ 表示成十位元二補數

先將 $+300$ 轉換成二進位：

因此：

逐位反相：

再加上 $1$：

所以：

3. 進行二進位加法

將兩個十位元二補數相加：

因此加法結果為：

最高位為 $1$，代表結果是負數，需將其解碼為十進位。

本題考查圖靈機 (Turing Machine) 的狀態圖設計，目標是設計一個能將輸入的二進位數字加一的圖靈機。

核心觀念：
圖靈機由一個有限的狀態集合、一個無限長的紙帶、一個讀寫頭以及一個轉移函數組成。轉移函數定義了在特定狀態和讀到特定符號時，圖靈機應該執行的動作：寫一個符號、移動讀寫頭（左或右）以及改變到下一個狀態。

題目要求：
設計一個圖靈機，使其能將紙帶上的二進位數字加一。
例如：

• 輸入 0100，輸出 0101 (加一)
• 輸入 0111，輸出 1000 (加一，有進位)

設計思路：
要將一個二進位數加一，我們需要從最低位 (最右邊) 開始處理。

1. 如果最低位是 0，將其變為 1，然後停止。
2. 如果最低位是 1，將其變為 0，並向左進位 (處理下一位)。
3. 重複進位過程，直到遇到 0 (將 0 變為 1 後停止)，或者紙帶的左邊沒有更多數字 (表示需要新增一個 1 在最高位)。
4. 圖靈機的紙帶通常是無限延伸的，我們假設紙帶上有輸入的二進位數，並且兩邊有足夠的空白符號 (例如 B 或 _)。

狀態設計：
我們可以定義以下幾個狀態：

• q_start：初始狀態。讀寫頭指向輸入二進位數的最右邊一位。
• q_process_rightmost：處理最右邊的位元。
• q_carry：處理進位。
• q_accept：接受狀態，表示運算完成。

紙帶符號：

• 0: 二進位數字 0。
• 1: 二進位數字 1。
• B: 紙帶的空白符號 (Blank)。

轉移函數 (Transition Function) $\delta(q, \text{read\_symbol}) \rightarrow (q', \text{write\_symbol}, \text{move\_direction})$

假設讀寫頭初始指向輸入二進位數的最右邊一位。

1. 從 q_start 開始：

   • 讀寫頭指向最右邊的數字。
   • $\delta(q_{start}, \text{'0'}) \rightarrow (q_{accept}, \text{'1'}, R)$
     • 如果看到 0，將其變為 1，然後右移（或停止），進入接受狀態。
   • $\delta(q_{start}, \text{'1'}) \rightarrow (q_{carry}, \text{'0'}, L)$
     • 如果看到 1，將其變為 0，然後向左移動，準備處理進位。
   • $\delta(q_{start}, B) \rightarrow (q_{accept}, \text{'1'}, R)$
     • 如果紙帶是空的 (只有空白符號)，則寫入 1，進入接受狀態。 (處理輸入為空或只有 0 的情況，例如 0 -> 1)

2. 處理進位 (從 q_carry 狀態)：

   • 我們已經將一個 1 變成了 0，現在需要向左移動處理進位。
   • $\delta(q_{carry}, \text{'0'}) \rightarrow (q_{accept}, \text{'1'}, R)$
     • 如果在左邊遇到 0，將其變為 1，進位結束，右移（或停止），進入接受狀態。
   • $\delta(q_{carry}, \text{'1'}) \rightarrow (q_{carry}, \text{'0'}, L)$
     • 如果在左邊遇到 1，將其變為 0，進位繼續，繼續向左移動。
   • $\delta(q_{carry}, B) \rightarrow (q_{carry}, \text{'1'}, L)$
     • 如果向左移動時遇到了空白符號 B，表示我們到達了數字的左邊界，需要在此處寫入 1 作為新的最高位，進位結束，繼續向左移動（或者直接進入接受狀態）。

狀態圖繪製：

• 節點 (States):

  • q_start (初始狀態)
  • q_carry (處理進位狀態)
  • q_accept (接受狀態)

• 邊 (Transitions):

  • 從 q_start：

    • 讀 0, 寫 1, 移 R -> q_accept
    • 讀 1, 寫 0, 移 L -> q_carry
    • 讀 B, 寫 1, 移 R -> q_accept (處理空輸入或 0 的情況，例如 0 -> 1)

  • 從 q_carry：

    • 讀 0, 寫 1, 移 R -> q_accept
    • 讀 1, 寫 0, 移 L -> q_carry
    • 讀 B, 寫 1, 移 L -> q_carry (或直接進入 q_accept，但繼續左移是為了完整性，確保所有進位都處理了)

範例分析：

1. 輸入 0100:

   • 假設讀寫頭在最右邊的 0。
   • q_start, 讀 0 $\rightarrow$ 寫 1, 移 R, 進入 q_accept。
   • 紙帶變成 0101。

2. 輸入 0111:

   • 假設讀寫頭在最右邊的 1。
   • q_start, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：0110，讀頭移到右邊的 1。
   • q_carry, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：0100，讀頭移到中間的 1。
   • q_carry, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：0000，讀頭移到左邊的 0。
   • q_carry, 讀 0 $\rightarrow$ 寫 1, 移 R, 進入 q_accept。 紙帶：1000，讀頭移到右邊的 0。
   • 紙帶變成 1000。

3. 輸入 1111:

   • q_start, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：1110
   • q_carry, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：1100
   • q_carry, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：1000
   • q_carry, 讀 1 $\rightarrow$ 寫 0, 移 L, 進入 q_carry。 紙帶：0000
   • q_carry, 讀 B (假設紙帶左邊是空白) $\rightarrow$ 寫 1, 移 L, 進入 q_carry。 紙帶：10000
   • 紙帶變成 10000。

總結狀態圖：

• 狀態：
  • $q_{start}$ (初始狀態)
  • $q_{carry}$ (進位處理狀態)
  • $q_{accept}$ (接受狀態)

核心觀念

本題考查由真值表建立組合邏輯電路，主要使用：

• 最小項（minterm）：每一列輸出為 $1$ 時，將該列寫成一個 AND 項。
• 積之和（Sum of Products, SOP）：將所有輸出為 $1$ 的最小項以 OR 相加。
• 布林代數化簡：合併相鄰最小項，消去不影響輸出的變數。

變數為 $a,b,c$，輸出記為 $F$。

解題方法：由輸出為 1 的列建立最小項

真值表中輸出為 $1$ 的組合為：

因此，直接寫成積之和：

接著進行化簡。

將後三項中的相鄰項合併：

因此可得：

這就是適合用 AND、OR、NOT gates 實作的化簡結果。

電路實作

令三個 AND 閘的輸出分別為：

最後使用一個 OR 閘：

因此電路需要：

1. 三個 NOT 閘，分別產生 $\overline{a}$、$\overline{b}$、$\overline{c}$。
2. 一個三輸入 AND 閘，計算 $\overline{a}\,\overline{b}\,\overline{c}$。

核心觀念

二元樹的兩種走訪定義如下：

• 前序走訪（Pre-order）：根節點 → 左子樹 → 右子樹
• 中序走訪（In-order）：左子樹 → 根節點 → 右子樹

當所有節點值皆不重複時，前序與中序走訪序列可以唯一決定一棵二元樹。

前序序列的第一個節點必定是目前子樹的根；找到該根在中序序列中的位置後，根左側是左子樹，根右側是右子樹。

解題方法

題目給定：

• 前序：F, B, A, D, C, E, G, I, H
• 中序：A, B, C, D, E, F, G, H, I

1. 找整棵樹的根節點

前序的第一個節點是 F，因此：

在中序序列中，F 將節點分成：

• 左子樹：A, B, C, D, E
• 右子樹：G, H, I

因此前序中接續的五個節點屬於左子樹：

• 左子樹前序：B, A, D, C, E
• 右子樹前序：G, I, H

2. 建立 F 的左子樹

左子樹前序序列為 B, A, D, C, E，因此根節點是 B。

左子樹的中序序列為 A, B, C, D, E。B 將其分成：

• B 的左子樹：A
• B 的右子樹：C, D, E

B 的右子樹前序序列為 D, C, E，因此其根節點是 D。

在中序序列 C, D, E 中，D 將其分成：

• D 的左子樹：C
• D 的右子樹：E

所以左半部結構為：

• B 的左子節點是 A
• B 的右子節點是 D
• D 的左子節點是 C
• D 的右子節點是 E

3. 建立 F 的右子樹

右子樹前序序列為 G, I, H，因此根節點是 G。

核心觀念

本題考查 $[7,4]$ Hamming Code。原始資料有 $4$ 個位元，加入 $3$ 個同位檢查位元後形成 $7$ 位元碼字，可偵測並修正單一位元錯誤。

同位元位置固定放在 $2$ 的次方位置：

因此資料位元放在：

採用偶同位（even parity），也就是每組檢查範圍中的 $1$ 總數必須為偶數。

解題方法

將資料序列 $1011$ 依序放入位置 $3,5,6,7$：

三個同位元的檢查範圍如下：

• $p_1$ 檢查位置 $1,3,5,7$
• $p_2$ 檢查位置 $2,3,6,7$
• $p_4$ 檢查位置 $4,5,6,7$

計算 $p_1$

位置 $1,3,5,7$ 的位元為：

為使 $1$ 的總數為偶數：

因為 $1\oplus0\oplus1=0$，所以：

計算 $p_2$

位置 $2,3,6,7$ 的位元為：

因此：

由於三個 $1$ 的 XOR 結果為 $1$：

所以：

計算 $p_4$

本題考查上下文無關文法 (Context-Free Grammar, CFG) 的應用，要求根據給定的文法規則，展示如何推導出一個句子，並繪製其分析樹 (Parse Tree)。

核心觀念：

1. 文法規則 (Production Rules): 定義了如何從一個非終端符號 (non-terminal symbol) 推導出其他符號（終端符號或非終端符號）。
2. 終端符號 (Terminal Symbols): 文法中最小的、不可再被分解的單詞或符號（例如：the, a, cat, flower, jumps, blooms）。
3. 非終端符號 (Non-terminal Symbols): 文法中可以被進一步推導的符號（例如：<sentence>, <noun-phrase>, <article>, <predicate>）。
4. 推導 (Derivation): 從起始符號 (start symbol) 開始，重複應用文法規則，逐步將非終端符號替換為其他符號，最終得到一個只包含終端符號的串 (sentence)。
5. 分析樹 (Parse Tree): 一種樹狀結構，用來表示一個句子是如何根據文法規則推導出來的。樹的根節點是起始符號，葉節點是終端符號，中間節點是非終端符號。

給定的文法規則：

1. <sentence> ::= <noun-phrase> <predicate>
2. <noun-phrase> ::= <article> <noun>
3. <article> ::= the | a | an
4. <noun> ::= cat | flower
5. <predicate> ::= jumps | blooms

推導過程 (Derivation)：
我們需要從起始符號 <sentence> 開始，逐步推導出一個合法的句子。這裡我們選擇其中一種可能的推導路徑。

1. 起始符號： <sentence>
2. 應用規則 1： <sentence> ::= <noun-phrase> <predicate>
   • 目前推導：<noun-phrase> <predicate>
3. 推導 <noun-phrase> (應用規則 2)： <noun-phrase> ::= <article> <noun>
   • 目前推導：<article> <noun> <predicate>
4. 推導 <article> (應用規則 3，選擇一個終端符號)： 例如，選擇 the。
   • 目前推導：the <noun> <predicate>
5. 推導 <noun> (應用規則 4，選擇一個終端符號)： 例如，選擇 cat。
   • 目前推導：the cat <predicate>
6. 推導 <predicate> (應用規則 5，選擇一個終端符號)： 例如，選擇 jumps。
   • 目前推導：the cat jumps

這是一個合法的句子，只包含終端符號。

另一種推導範例：

1. <sentence>
2. <noun-phrase> <predicate>
3. <article> <noun> <predicate>
4. a <noun> <predicate>
5. a flower <predicate>
6. a flower blooms

本題考查網路通訊協定與位址相關的基本概念，要求解釋並比較兩兩術語的異同。

核心觀念：

• 網路分層模型 (OSI/TCP/IP): 理解不同協定在網路堆疊中的位置。
• 網路位址 (Network Addressing): 邏輯位址與實體位址的區別。
• 資料傳輸與錯誤檢查 (Data Transmission & Error Checking): 協定在確保資料完整性方面的作用。

(a) DNS (Domain Name System) and ARP (Address Resolution Protocol)

• DNS (Domain Name System):

  • 解釋： DNS 是一個分佈式的命名系統，用於將人類可讀的網域名稱 (如 www.example.com) 轉換為機器可讀的 IP 位址 (如 192.168.1.100)。它工作在應用層 (Application Layer)。
  • 功能： 域名解析。
  • 位址轉換： 網域名稱 $\leftrightarrow$ IP 位址。
  • 層級： 應用層。

• ARP (Address Resolution Protocol):

  • 解釋： ARP 是一種網路協定，用於將 IP 位址 (網路層位址) 解析為 MAC 位址 (資料鏈結層位址)。它工作在網路層和資料鏈結層之間。
  • 功能： IP 位址 $\leftrightarrow$ MAC 位址 解析。
  • 位址轉換： IP 位址 $\leftrightarrow$ MAC 位址。
  • 層級： 網路層與資料鏈結層之間。

• 相似性：

  • 兩者都是用於「解析」或「轉換」不同類型的位址，以便網路通訊能夠進行。
  • 兩者都扮演著「翻譯」的角色，讓不同層級的協定能夠互相溝通。

• 主要差異：

  • 轉換的位址類型： DNS 轉換網域名稱與 IP 位址；ARP 轉換 IP 位址與 MAC 位址。
  • 工作層級： DNS 工作在應用層；ARP 工作在網路層與資料鏈結層之間。
  • 目的： DNS 的主要目的是方便使用者訪問網路資源（通過易記的名稱）；ARP 的主要目的是讓資料封包能夠在區域網路 (LAN) 中被正確地傳遞到目標設備。ARP 解決的是「在區域網路內，如何找到下一跳的硬體位址」的問題。

(b) IPv4 address and MAC address

• IPv4 address (Internet Protocol version 4 address):

  • 解釋： IPv4 位址是一個 32 位的邏輯位址，用於在網際網路 (Internet) 上唯一標識一個設備。它由網路層分配，可以被重新設定或分配。
  • 格式： 通常表示為四組數字，每組 0-255，用點分隔 (e.g., 192.168.1.100)。
  • 層級： 網路層 (Network Layer)。
  • 作用： 在廣域網 (WAN) 或跨網路的通訊中，用於路由封包。
  • 分配： 由網路管理員、ISP 或 DHCP 伺服器分配。

• MAC address (Media Access Control address):

  • 解釋： MAC 位址是一個 48 位的實體位址 (或硬體位址)，燒錄在網路介面卡 (NIC) 中，是全球唯一的。它屬於資料鏈結層。
  • 格式： 通常表示為六組十六進位數字，每組兩位，用冒號或連字號分隔 (e.g., 00:1A:2B:3C:4D:5E)。
  • 層級： 資料鏈結層 (Data Link Layer)。
  • 作用： 在區域網路 (LAN) 段內，用於識別網路上的具體設備，進行區域網路傳輸。
  • 分配： 由硬體製造商在生產時分配，通常不能更改。

• 相似性：

  • 兩者都是用於在網路上唯一識別網路設備。
  • 兩者都是數據傳輸過程中必需的位址資訊。

• 主要差異：

  • 性質： IPv4 是邏輯位址，可變；MAC 是實體位址，固定。
  • 層級： IPv4 在網路層；MAC 在資料鏈結層。
  • 範圍： IPv4 用於廣域網路路由；MAC 用於區域網路內的傳輸。
  • 唯一性： IPv4 在一個網路範圍內唯一（或全球唯一，取決於公有/私有）；MAC 位址在全球範圍內理論上是唯一的。
  • 分配方式： IPv4 可動態或靜態分配；MAC 由硬體製造商固定。

(c) Internet checksum and Cyclic Redundancy Check (CRC)

• Internet checksum:
  • 解釋： 是一種用於檢測網路層 (IP) 和傳輸層 (TCP, UDP) 數據報頭中內容的錯誤的演算法。它是一種基於一次性求和 (one's complement sum) 的校驗和。
  • 位置： 通常計算數據報頭 (header) 的校驗。在 IP、ICMP、UDP、TCP 協定中都有應用。
  • 演算法： 將數據頭的 16 位字元組 (words) 相加（使用一次性求和），然後對結果取反。
  • 目的： 快速檢測數據頭的錯誤，但不能糾正錯誤。
  • 可靠性： 相對較弱，不能檢測所有類型的錯誤（例如，位元翻轉和位元交換的組合錯誤可能無法被檢測）。

核心觀念

本題考查 8086 的：

• CX 暫存器與 16 位元計數。
• DEC CX：先將 CX 減 1，並依結果設定旗標。
• JNZ（Jump if Not Zero）：當零旗標 $ZF=0$ 時跳躍。
• 迴圈次數的計算，以及跳躍標籤位置對程式流程的影響。

DEC CX 的結果為 $0$ 時，會使 $ZF=1$；結果不為 $0$ 時，則 $ZF=0$。因此：

解題方法與程式流程

題目程式如下：

DLY:
    MOV CX, 1000H
    DEC CX
    NOP
    JNZ DLY
NXT:

依照程式實際執行順序：

1. MOV CX, 1000H：將 CX 設為 $1000_H=4096$。
2. DEC CX：將 CX 減 1，變成 $0FFF_H=4095$。
3. NOP：不執行任何有效運算，只消耗一個指令週期。
4. JNZ DLY：因為 CX=0FFFH，結果不為 0，故 $ZF=0$，跳回 DLY。
5. 跳回後再次執行 MOV CX,1000H，CX 又被重設為 4096。

因此，每次執行到 JNZ DLY 時，CX 都會重新經過：

永遠不會遞減到 $0$，所以程式會形成無限迴圈，NXT 永遠不會執行。

(a) 各指令執行功能

• MOV CX, 1000H
  將十六位元常數 $1000_H$ 載入 CX。

• DEC CX
  將 CX 減 1。第一次執行後：

  $$CX=1000_H-1=0FFF_H$$

• NOP
  No Operation，不改變暫存器或資料，只執行空操作。

• JNZ DLY
  若零旗標 $ZF=0$，跳回標籤 DLY；若 $ZF=1$，則繼續執行下一個位置。

由於 DLY 放在 MOV CX,1000H 前方，跳回後會重新載入 CX，造成無限迴圈。

本題考查二元搜尋法 (Binary Search) 的實作，要求撰寫一個二元搜尋函數，並在主程式中呼叫此函數來搜尋排序好的整數陣列中的元素。

核心觀念：

• 二元搜尋法： 一種在已排序陣列中搜尋目標值的搜尋演算法。它的時間複雜度為 $O(\log n)$。
• 演算法步驟：
  1. 設定搜尋範圍的起始 (low) 和結束 (high) 索引。
  2. 當 low $\le$ high 時，計算中間索引 mid = (low + high) / 2。
  3. 比較目標值與陣列中 mid 位置的值：
     • 如果目標值等於 mid 位置的值，則找到目標，返回 mid。
     • 如果目標值小於 mid 位置的值，則在左半部繼續搜尋 (high = mid - 1)。
     • 如果目標值大於 mid 位置的值，則在右半部繼續搜尋 (low = mid + 1)。
  4. 如果迴圈結束 (low > high)，表示目標值不在陣列中，返回一個表示未找到的值（例如 -1）。
• 主程式 (Main Program)： 負責準備測試數據（排序好的陣列、目標值）並呼叫搜尋函數，然後輸出結果。

程式設計語言選擇：
可以使用 Python, C++, Java, C# 等任一種高階程式語言。這裡選擇 Python，因為其語法簡潔易懂。

Python 實作：

1. 二元搜尋函數 (binary_search):

def binary_search(arr, target):
    """
    Performs binary search on a sorted array.

    Args:
        arr: A sorted list of integers.
        target: The integer to search for.

    Returns:
        The index of the target in the array if found, otherwise -1.
    """
    low = 0
    high = len(arr) - 1

    while low <= high:
        # Calculate mid index. Using (low + high) // 2 can cause overflow for very large arrays,
        # but in Python this is less of a concern due to arbitrary precision integers.
        # A safer way is low + (high - low) // 2.
        mid = low + (high - low) // 2

        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target is smaller than mid, then it can only be present in left subarray
        elif arr[mid] > target:
            high = mid - 1
        # Else the target can only be present in right subarray
        else:
            low = mid + 1

    # If we reach here, then the element was not present
    return -1

2. 主程式 (Main Program):

# --- Binary Search Function (as defined above) ---
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            high = mid - 1
        else:
            low = mid + 1
    return -1

# --- Main Program ---
if __name__ == "__main__":
    # 1. Prepare a sorted integer array
    sorted_array = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
    print(f"Sorted array: {sorted_array}")

    # 2. Define target elements to search for
    targets_to_search = [23, 38, 2, 91, 7, 100] # Includes elements present and absent

    # 3. Iterate through targets and use binary search
    for target_value in targets_to_search:
        print(f"\nSearching for: {target_value}")
        result_index = binary_search(sorted_array, target_value)

        # 4. Output the result
        if result_index != -1:
            print(f"Element {target_value} found at index: {result_index}")
        else:
            print(f"Element {target_value} not found in the array.")

程式碼解釋：

• binary_search(arr, target) 函數：
  • 接收一個已排序的列表 arr 和要搜尋的目標值 target。
  • 初始化 low = 0 (陣列起始索引) 和 high = len(arr) - 1 (陣列結束索引)。
  • while low <= high: 迴圈持續進行，直到搜尋範圍縮小到空（low 變得大於 high）。
  • mid = low + (high - low) // 2: 計算中間索引。這種計算方式可以避免潛在的整數溢位問題（雖然在 Python 中不太常見，但在其他語言中很重要）。
  • if arr[mid] == target:: 如果中間元素就是目標值，則返回其索引 mid。
  • elif arr[mid] > target:: 如果中間元素大於目標值，說明目標值（如果存在）一定在左半部分，因此將 high 更新為 mid - 1。
  • else: (即 arr[mid] < target): 如果中間元素小於目標值，說明目標值（如果存在）一定在右半部分，因此將 low 更新為 mid + 1。