在排序陣列中查找值是一項非常簡單的任務，這些陣列可能包含重復性并將索引回傳到單行的標準輸出。
輸入的第一行包含數字N和k，用空格分隔。
- N是數字的數量，k是要執行的查詢數量。
- 下一行或多行包含N 個非遞減順序的數字（資料）和 k 個數字（查詢）以在輸入序列中搜索。
- 數字由空格和行尾分隔。
將資料讀入記憶體，并為每個請求找到它在序列中的第一個位置i（即data[i]=x的最小值i）。位置索引從 1 到N。
在一行中將所有這些索引寫入標準輸出，用空格分隔。如果序列中不存在請求的數字，則輸出 0 而不是其位置。如果該數字出現多次，則輸出其第一次出現的索引。序列的大小 ( N ) 和請求的數量 ( k ) 最多為 1 000 000。
def custom_search(arr, target) -> int:
n = len(arr) 1
for i in range(1, n):
if (arr[i-1] == target):
return(i)
return(0)
def give_numbers():
inputs = list(map(int, input().split()))
if len(inputs) != 2:
return([], None, None)
n, m = inputs
if ((n < 1 or n > 1000000) or (m < 1 or m > 1000000)):
return([], None, None)
i = 2
stuff = []
while i >= 1:
stuff.append(list(map(int, input().split())))
i -= 1
return(stuff, n, m)
inpt, n, m = give_numbers()
if len(inpt) != 0:
N, k = inpt
if n == len(N) and m == len(k):
for i in k:
print(custom_search(N, i), end=" ")
Inputs:
10 4
4 8 9 9 9 9 18 28 32 100
4 9 28 32
Outputs:
1 3 8 9
有沒有更好的方法來避免在有序陣列中搜索 O(n) 并加快速度？
uj5u.com熱心網友回復：
您是否考慮過實施某種二進制搜索？將陣列分成兩半，如果搜索到的值大于中間值，則取第二部分并繼續。在偽代碼中：
found = false
while(!found && array.length > 1){
i = array.length / 2;
if (array[i]==searchedValue) return true
if (array[i]>searchedValue) array = array.slice(0, i)
if (array[i]<searchedValie) array = array.slice(i 1, array.length)
}
if (array[0] == searchedValue) found = true
return found
這將把復雜度降低到 O(log(n))
uj5u.com熱心網友回復：
您可以使用修改后的二分搜索，它可以在給定陣列中找到給定目標的最左邊出現：
int binsearchLeftmost(int l, int r, int target, const std::vector<int>& array) {
int res = 0;
while (l <= r) {
int m = l (r - l) / 2;
if (array[m] > target) {
r = m - 1;
}
else if (array[m] < target) {
l = m 1;
}
else {
res = m 1;
r = m - 1;
}
}
return res;
}
uj5u.com熱心網友回復：
您要查找的演算法稱為二分查找，其時間復雜度為 O(log2(N))。
這是一個有 2 個引數的 python 函式：
- 您正在尋找的價值
- 排序后的陣列
它回傳第一個位置 i，其中 array[i] = value
def find_first_appearence(value, array):
position = 0
left = 0;
right = len(array) - 1
while left <= right:
middle = int(left (right - left) / 2)
if array[middle] >= value:
right = middle - 1
position = middle
else:
left = middle 1
if array[position] != value:
return 0
return position
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/340986.html