In Python gibt es hauptsächlich zwei Suchalgorithmen, die hauptsächlich verwendet werden. Davon ist die erste die lineare Suche und die zweite die binäre Suche.
Diese beiden Techniken werden hauptsächlich verwendet, um ein Element aus dem angegebenen Array oder auch aus der angegebenen Liste zu durchsuchen. Bei der Suche nach einem Element gibt es zwei Methoden, die in jedem Algorithmustyp angewendet werden können. Einer davon ist der rekursive Ansatz und der andere der iterative Ansatz. Lassen Sie uns beide Algorithmen in beiden Ansätzen diskutieren und ähnliche Probleme lösen.
Die lineare Suchtechnik wird auch als sequentielle Suche bezeichnet. Die Bedeutung des Namens „Sequentielle Suche“ wird eindeutig durch den Prozess gerechtfertigt, dem dieser Suchalgorithmus folgt. Es handelt sich um eine Methode oder Technik, die verwendet wird, um die Elemente in einem Array oder einer Liste in Python zu finden.
它被认为是所有其他搜索算法中最简单和最容易的.但是,这个算法的唯一缺点是效率不高。这就是为什么不经常使用线性搜索的主要原因.
Schritt 1 - Es wird in sequentieller Reihenfolge nach einem Element gesucht, indem einfach das gewünschte Element mit jedem im angegebenen Array vorhandenen Element verglichen wird.
Schritt 3 − Wenn das Element nicht im Array vorhanden ist, wird der Benutzer darüber informiert, dass das Element nicht gefunden wurde. Auf diese Weise wird der Algorithmus verarbeitet.
Im Allgemeinen ist der lineare Suchalgorithmus vergleichsweise geeignet und effizient für kleine Arrays oder kleine Listen mit einer Größe kleiner oder gleich 100, da er jedes Element überprüft und vergleicht.
在下面的示例中,我们将学习使用线性搜索在数组中查找元素的过程.
def iterative_linear( arr, n, key_element):
for x in range(n):
if(arr[x] == key_element):
return x
return -1
arr = [2, 3, 5, 7, 9, 1, 4, 6, 8, 10]
max_size = len(arr)
key = 8
result = iterative_linear(arr, max_size - 1, key)
if result != -1:
print ("The element", key," is found at the index " ,(result), "and in the ", (result+1), "position")
else:
print ("The element %d is not present in the given array" %(key))
The element 8 is found at the index 8 and in the 9 position
Beispiel (Rekursiv)
def recursive_linear( arr, first_index, last_index, key_element):
if last_index < first_index:
return -1
if arr[first_index] == key_element:
return first_index
if arr[last_index] == key_element:
return last_index
return recursive_linear(arr, first_index + 1, last_index - 1, key_element)
arr = [2, 3, 5, 7, 9, 1, 4, 6, 8, 10]
max_size = len(arr)
key = 8
result = recursive_linear(arr, 0, max_size - 1, key)
if result != -1:
print ("The element", key," is found at the index " ,(result), "and in the ", (result+1), "position")
else:
print ("The element %d is not present in the given array" %(key))
Ausgabe
The element 8 is found at the index 8 and in the 9 position
Binäre Suche
如果数组在某些情况下没有排序,则对数组进行排序,然后开始二分搜索算法的过程.一旦数组被二分搜索算法考虑，它首先被排序，然后算法被应用于数组。
步骤 1
Schritt 2 − Nachdem das Array sortiert wurde, wird das Array als zwei Hälften betrachtet. Eine Hälfte beginnt vom ersten Element bis zum mittleren Element des sortierten Arrays und die zweite Hälfte beginnt vom Element nach dem mittleren Element bis zum letzten Element des sortierten Arrays.
Schritt 3 - Das Schlüsselelement (das zu durchsuchende Element wird als Schlüsselelement bezeichnet) wird mit dem mittleren Element des sortierten Arrays verglichen.
Schritt 4 - Wenn das Schlüsselelement kleiner oder gleich dem mittleren Element des sortierten Arrays ist, werden die Elemente der zweiten Hälfte weiterhin ignoriert, da das Schlüsselelement kleiner als das mittlere Element ist. Das Element muss also auf jeden Fall zwischen dem ersten Element und dem mittleren Element vorhanden sein.
Schritt 6 − Wenn das Schlüsselelement größer als das mittlere Element ist, wird die erste Hälfte des sortierten Arrays ignoriert und die Elemente vom mittleren bis zum letzten Element werden berücksichtigt.
Schritt 7 − Von diesen Elementen wird das Schlüsselelement erneut mit dem mittleren Element des halbierten Arrays verglichen und der gleiche Vorgang wiederholt. Wenn das Schlüsselelement größer als das mittlere Element des halbierten Arrays ist, wird die erste Hälfte vernachlässigt.
第8步 - 如果关键元素小于或等于被分割数组的中间元素，则被分割数组的后半部分将被忽略。通过这种方式，元素将在数组的任意一半中进行搜索。
因此，与线性搜索相比，复杂度减少了一半或更多，因为有一半的元素将在第一步中被移除或不被考虑。二分搜索的最佳情况时间复杂度为“O(1)”。二分搜索的最坏情况时间复杂度为“O(logn)”。这就是二分搜索算法的工作原理。让我们考虑一个例子，并应用二分搜索算法来找出数组中的关键元素。
In this example, we are going to learn about the process of searching an element in an array using Binary search in recursive approach.
def recursive_binary(arr, first, last, key_element):
if first <= last:
mid = (first + last) // 2
if arr[mid] == key_element:
return mid
elif arr[mid] > key_element:
return recursive_binary(arr, first, mid - 1, key_element)
elif arr[mid] < key_element:
return recursive_binary(arr, mid + 1, last, key_element)
else:
return -1
arr = [20, 40, 60, 80, 100]
key = 80
max_size = len(arr)
result = recursive_binary(arr, 0, max_size - 1, key)
if result != -1:
print("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
上述程序的输出如下：
The element 80 is found at the index 3 and in the position 4
In this example, we are going to learn about the process of searching an element in an array using Binary search in iterative approach.
def iterative_binary(arr, last, key_element):
first = 0
mid = 0
while first <= last:
mid = (first + last) // 2
if arr[mid] < key_element:
first = mid + 1
elif arr[mid] > key_element:
last = mid - 1
else:
return mid
return -1
arr = [20, 40, 60, 80, 100]
key = 80
max_size = len(arr)
result = iterative_binary(arr, max_size - 1, key)
if result != -1:
print("The element", key, "is present at index", (result), "in the position", (result + 1))
else:
print("The element is not present in the array")
上述程序的输出如下：
The element 80 is found at the index 3 and in the position 4
这是二分搜索算法的工作原理。根据时间复杂度的概念，我们可以肯定二分搜索算法比线性搜索算法更高效，时间复杂度在其中起着重要的作用。通过使用这种类型的算法，可以搜索数组中的元素。尽管用于解决问题的过程不同，但结果不会波动。这是使用多种算法检查输出一致性的一个优点。
Das obige ist der detaillierte Inhalt vonPython-Programm zur Suche nach Elementen im Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
So fügen Sie ein Video in HTML ein
Gängige Tools zum Softwaretesten
Einführung in die Rolle von Cloud-Servern
Der Unterschied zwischen Heap und Stack
Wie lautet die E-Mail-Adresse und wie wird sie ausgefüllt?
So verwenden Sie die JSP-Programmiersoftware
So kaufen Sie Ripple in China
Mehrere Möglichkeiten zur Datenerfassung
