首頁猿問搜索數(shù)組報告“找不到&...

搜索數(shù)組報告“找不到”，即使找到了

算法與數(shù)據(jù)結(jié)構(gòu) 源碼

MYYA 2019-07-11 12:38:34

搜索數(shù)組報告“找不到”，即使找到了這是一個通用的問題和答案，這是一個邏輯錯誤，我在許多來自不同語言的新程序員的問題中看到過。問題是在數(shù)組中搜索與某些輸入條件匹配的元素。該算法，在偽代碼中，如下所示：for each element of Array: if element matches criteria: do something with element maybe break out of loop (if only interested in first match) else: print "Not found"此代碼報告“未找到”，即使它成功地找到了匹配的元素。

查看完整描述

1 回答

慕斯709654

TA貢獻1840條經(jīng)驗獲得超5個贊

問題是，當您在數(shù)組中線性地搜索某物時，直到到達數(shù)組的末尾，您才能知道它是否被找到。問題中的代碼報告了每個不匹配元素的“未找到”，即使可能有其他匹配元素。

簡單的修改是使用一個變量來跟蹤您是否找到了什么，然后在循環(huán)結(jié)束時檢查這個變量。

found = false
for each element of Array:
    if element matches criteria:
        do something with element
        found = true
        maybe break out of loop (if only interested in first match)

if not found:
    print "Not found"

Python有一個else:分塊for循環(huán)。這只在循環(huán)運行到完成時執(zhí)行代碼，而不是由于使用break..這使您可以避免found變量(盡管它對以后的處理仍然有用)：

for element in someIterable:
    if matchesCriteria(element):
        print("Found")
        break
else:
    print("Not found")

有些語言有內(nèi)置機制，可以用來代替編寫自己的循環(huán)。

有些語言有一個
any
或
some
函數(shù)，該函數(shù)接受回調(diào)函數(shù)，并返回一個布爾值，指示數(shù)組中的任何元素是否成功。
如果語言具有數(shù)組過濾功能，則可以使用檢查條件的函數(shù)過濾輸入數(shù)組，然后檢查結(jié)果是否為空數(shù)組。
如果要與元素完全匹配，大多數(shù)語言都會提供
find
或
index
函數(shù)，該函數(shù)將搜索匹配的元素。

如果要經(jīng)常進行搜索，最好將數(shù)組轉(zhuǎn)換為可以更有效地搜索的數(shù)據(jù)結(jié)構(gòu)。大多數(shù)語言提供set和/或hash table數(shù)據(jù)結(jié)構(gòu)(后者根據(jù)語言使用多個名稱，例如關(guān)聯(lián)數(shù)組、映射、字典)，這些結(jié)構(gòu)通常可以在O(1)時間內(nèi)搜索，而掃描數(shù)組則是O(N)。

反對回復 2019-07-11