tags: APCS

d732－二分搜尋法

題目連結： d732

題目解析

這道題目要求在一個嚴格遞增的數列中，檢查多個詢問數是否存在於數列中，如果存在則返回其在數列中的位置，否則返回 0。

解題方向

• 使用二分搜尋法：
  • 因為數列是嚴格遞增的，所以可以使用二分搜尋法來有效地查找某個數是否存在於數列中。
  • 二分搜尋法的時間複雜度是 O(logn)，適合用來處理大量數據的查找問題。
• 處理多個詢問數：
  • 對於每個詢問數，使用二分搜尋法在數列中查找其位置，並輸出結果。

程式解析

範例輸入

5 5
1 3 4 7 9
3 1 9 7 -2

範例輸出

2
1
5
4
0

• 輸入讀取：
  • 第一行讀取數列長度 𝑛 和詢問數 𝑘 。
  • 第二行讀取長度為 𝑛 的嚴格遞增數列。
  • 第三行讀取 𝑘 個詢問的整數。
• 二分搜尋法查找：
  • 對每個詢問數使用二分搜尋法查找其在數列中的位置，若找到則返回其索引（索引從 1 開始），若未找到則返回 0。
• 輸出結果：
  • 逐個輸出每個詢問數的查找結果。

完整程式碼

import sys

def search(arr, lens, num):
    lower = 0
    upper = lens - 1

    # 二分搜尋法查找位置，位置要改成從1開始，所以return要+1
    while lower <= upper:
        mid = (lower + upper) // 2
        if num > arr[mid]:
            lower = mid + 1
        elif num < arr[mid]:
            upper = mid - 1
        else:
            return mid + 1

    # 找不到 num，返回 0
    return 0

# 讀取輸入
s = input()
s = [int(i) for i in s.split()]

N = s[0]
K = s[1]

data = input()
data = list(map(int, data.split()))

query = input()
query = list(map(int, query.split()))

# 對每個詢問數使用二分搜尋法查找並輸出結果
for i in query:
    print(search(data, len(data), i))