Bir öğeyi keşfetmek için gereken doğrudan karşılaştırma sayısını azaltmak amacıyla, bir öğe koleksiyonunu İkili Arama'da iki yarıya böldük. Ancak bir gereklilik vardır: Dizinin öğelerinin önceden sıralanması gerekir.

Ikili arama

Ikili arama Yöntem belirli bir liste üyesinin dizinini bulur. En popüler ve en hızlı algoritmalar arasındadır. İkili Arama prosedürünün çalışması için listedeki girişlerin sıralanması gerekir.

Ikili arama bir öğenin indeksini bulmak için daha etkili bir arama tekniğidir. Doğrusal Arama çünkü her liste indeksini incelemek zorunda değiliz.

İkili Arama Algoritmasının tüm işleyişi aşağıdaki adımlarla özetlenebilir:

• Sıralanan dizide ortadaki öğeyi bulun.
• Yerleştirilecek eleman ile ortadaki eleman arasında bir karşılaştırma yapın.
• Eğer bu eleman verilen listenin orta elemanına eşitse orta elemanın indeksi döndürülür. Aksi takdirde algoritma, öğeyi ortadaki öğeyle karşılaştıracaktır.
• Şimdi, eğer konumu belirlenecek öğe listenin orta öğesinden büyükse listenin sağ yarısıyla, yani orta dizinden sonraki öğelerle karşılaştırılacaktır.
• Veya eleman listenin ortasındaki elemandan küçükse, o zaman listenin yalnızca sol yarısıyla, yani orta indeksten önceki elemanlarla karşılaştırılacaktır.

Özyinelemeli İkili Arama

İkili Arama, sıralanmış bir dizideki bir öğeyi keşfetmek için arama aralığını sürekli olarak 2 eşit parçaya bölmeyi ifade eder ve yinelenen ikili Arama, ikili arama prosedürünün tamamını daha küçük konulara ayırmayı gerektirir. Özyinelemeli ikili arama, ikili aramaya yönelik yinelemeli yanıttır.

Tüm özyinelemeli çözümlerin karşılaması gereken özellikler şunlardır:

1. Özyinelemeli bir yaklaşım için bir temel durum gereklidir.
2. Özyinelemeli bir yaklaşımda yinelemeli bir test senaryosu olmalıdır.
3. Özyinelemeli bir yaklaşımın temel duruma yaklaşması gerekir.

Karmaşık bir problemin en alt alt bölümü, son durum olan bir temel durumla temsil edilir. Bu nedenle, özyinelemeli yöntemle ikili Aramayı gerçekleştirmek için, algoritmamızın bir temel durum ve bir özyinelemeli durum içermesi gerekir; yinelemeli durum temel duruma doğru ilerlemelidir. Aksi halde süreç hiçbir zaman tamamlanamayacak ve sonsuz bir döngüye yol açacaktır.

İkili arama tekniği, sıralanmış bir dizi içindeki belirli bir öğeyi bulmak için gereken süreyi azaltır. İkili arama yöntemi sıklıkla yinelemeli olarak uygulanır, ancak onu daha küçük parçalara bölerek yinelemeli olarak da uygulayabiliriz.

Kod

 #defining a function to execute Binary Search on any given sorted list L. #start is the lowest index of the list being checked at any given time. #end is the highest index of the list being checked at any given time. #item is the item to be searched in the list. def binary_search(L, start, end, item): if end >= start: middle = (start + end) // 2 if L[middle] == item: return middle #middle element is the item to be located #if middle item is greater than the item to be searched, left side of the list will be searched elif L[middle] > item: #starting index will be same but ending index will be the middle of the main list i.e. left half of the list is given in function. return binary_search(L, start, middle - 1, item) else: #if middle item is smaller than the item to be searched, new starting index will be middle of the list i.e. right half of the list. return binary_search(L, middle + 1, end, item) else: #if element is not present in the list return -1 #Drivers code my_list = [ 2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22 ] element_to_search = 6 print('The given list is') print(my_list) index_of_element = binary_search(my_list, 0, len(my_list)-1, element_to_search) if index_of_element != -1: print('Element searched is found at the index ', str(index_of_element), 'of given list') else: print('Element searched is not found in the given list!') 

Çıktı:

 The given list is [2, 4, 6, 9, 12, 16, 18, 19, 20, 21, 22] Element searched is found at the index 2 of given list 

Özyineleme son derece güçlü bir programlama ve problem çözme tekniğidir. Bunu, basit yinelemeli sorunlardan karmaşık geri izleme sorunlarına kadar çeşitli algoritmaları değerlendirmek ve yürütmek için kullanabiliriz. Bu derste, özyinelemeli ikili arama yöntemini oluşturmak için Python dilini kullanmayı inceledik.