Yazdığımız programlarda kullandığımız algoritmalar da her zaman en stabil ve hızlı yolu seçmeliyiz.
Bu yüzden Arama algoritmalarını iyi öğrenmeliyiz.
Sequential (Linear) Search with Unordered List
Bu yüzden Arama algoritmalarını iyi öğrenmeliyiz.
Sequential (Linear) Search with Unordered List
Sequential Search sıralı arama demektir.
Kod:
[COLOR="dimgray"]Unordered list ise bir listenin içerisinde ki değerlerin *sırasız* bir şekilde bulunduğu listelerdir.
[/COLOR] * [5, 7, 2, 3, 15, 8, 100, 12]Örneğin 8 sayısı, 5 den başlayarak teker teker 8 bulunana kadar gider.
5-7-2-3-15-8-STOP
Code:
OUT:
Kod:
[COLOR="Teal"]def sequentialSearchUnorderedList(liste,value):
"""
sequantial search for unordered list
"""
index = 0
found = False
while index < len(liste) and not found:
if liste[index] == value:
found = True
else:
index += 1
return (found,index)
liste = [5, 7, 2, 3, 15, 8, 100, 12]
found , index = sequentialSearchUnorderedList(liste, 15)
print(found)
print(index)
[/COLOR]OUT:
Kod:
[COLOR="darkgreen"]True
4
[/COLOR]
Sequential (Linear) Search with Ordered List
Bu arama algoritmasında listemiz düzenli olarak artmaktadır. Örneklersek
[2,4,6,8,10,12,14,16,...]
Şimdi kullanıcı 15 sayısını aratmak istiyor. Ama bu liste 2 şer 2 şer artıyor ve 14 sayısını geçtikten sonra 16 gelicek ve asla 15 i bulamayacak. O yüzden burada bulunamadı gibi bir hatayı vermek için tüm listenin taranmasına gerek yok.
Eğer verdiğimiz değerden büyük bir değer okursak döngümüzü sonlandırıyor.
Code:
Kod:
[COLOR="Teal"]def sequentialSearchOrderedList(liste,value):
"""
sequential search for ordered list
"""
index = 0
found = False
stop = False
while index < len(liste) and not found and not stop:
if liste[index] == value:
found = True
else:
if value < liste[index]:
stop = True
else:
index += 1
return (found,index)
liste = [2, 3, 5, 7, 8, 12, 15, 100]
found,index = sequentialSearchOrderedList(liste,6)
print(found)
print(index)
liste = [2, 3, 5, 7, 8, 12, 15, 100]
found,index = sequentialSearchOrderedList(liste,6)
print(found)
print(index)[/COLOR]Out:
Kod:
[COLOR="DarkGreen"]
False
3
[/COLOR]Binary Search
Gelelim asıl konumuz olan binary searche.
Binary search en avantıjlı algoritmalardan biridir.
Bu listede de küçükten büyüğe doğru sıralanmış olması gerekir.
Kısaca şöyle bahsedeyim
[1,2,6,9,12,15,24,34,75]
İstek = 6 sayısı kaçıncı index de dedir?
Algoritma:
Listenin ortasındaki değere bak = 12
Değer isteğe eşit mi = Hayır
Devam et
Değer İstekden büyük mü?
Evet
Sol tarafa bak.
Döngüyü başa al...
Şimdi bir örnek yapalım.
Code :
Kod:
[COLOR="Teal"]def binarySearch(liste,value):
"""
binary search for sorted array (sirali liste)
"""
first_index = 0
last_index = len(liste) - 1
found = False
while first_index <= last_index and not found:
middle_index = int((first_index + last_index)/2)
if liste[middle_index] == value:
found = True
else:
# lower half
if value < liste[middle_index]:
last_index = middle_index - 1
print("lower half")
# upper half
else:
first_index = middle_index + 1
print("upper half")
return found
[/COLOR]Out:
Kod:
[COLOR="DarkGreen"]liste = [3,6,11,12,18,21,34]
>>>binarySearch(liste,3)
*lower half
*lower half
*True
>>>binarySearch(liste,5)
*lower half
*lower half
*upper half
*False
>>>binarySearch(liste,18)
*upper half
*lower half
*True[/COLOR]
Son düzenleme:
