###### tags: `APCS`
# **d732－二分搜尋法**
### **題目連結：** [**d732**](https://zerojudge.tw/ShowProblem?problemid=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))