Bu eğitimde, verilen listede bir öğenin dizin konumunu bulmak için Python kullanarak ikili arama algoritmasını nasıl uygulayabileceğimizi öğreneceğiz.
cpld vs fpga
giriiş
İkili arama, listedeki belirli bir öğeyi bulmaya yönelik bir algoritmadır. Binlerce öğeden oluşan bir listemiz olduğunu ve belirli bir öğenin dizin konumunu almamız gerektiğini varsayalım. İkili arama algoritmasını kullanarak elemanın indeks konumunu çok hızlı bulabiliriz.
Pek çok arama algoritması vardır ancak ikili arama bunlar arasında en popüler olanıdır.
İkili arama algoritmasının uygulanabilmesi için listedeki öğelerin sıralanması gerekir. Öğeler sıralanmamışsa önce bunları sıralayın.
İkili arama kavramını anlayalım.
İkili Arama Kavramı
İkili arama algoritmasında eleman konumunu aşağıdaki yöntemleri kullanarak bulabiliriz.
- Özyinelemeli Yöntem
- Yinelemeli Yöntem
Böl ve yönet yaklaşımı tekniğini yinelemeli yöntem takip etmektedir. Bu yöntemde bir fonksiyon, listede bir öğe bulana kadar kendisini tekrar tekrar çağırır.
Yinelemeli yöntemde bir öğenin dizin konumunu bulmak için bir dizi ifade birden çok kez tekrarlanır. sırasında Döngü bu görevi gerçekleştirmek için kullanılır.
İkili arama, doğrusal aramaya göre daha etkilidir çünkü her liste dizinini aramamıza gerek yoktur. İkili arama algoritmasını elde etmek için listenin sıralanması gerekir.
İkili aramanın adım adım uygulanmasına bakalım.
Sıralanmış bir öğe listemiz var ve 45'lik dizin konumunu arıyoruz.
[12, 24, 32, 39, 45, 50, 54]
Böylece listemize iki işaretçi koyuyoruz. Bir işaretçi, adı verilen daha küçük değeri belirtmek için kullanılır. Düşük ve ikinci işaretçi, çağrılan en yüksek değeri belirtmek için kullanılır. yüksek .
ekran boyutu nasıl öğrenilir
Daha sonra değerini hesaplıyoruz. orta dizideki öğe.
mid = (low+high)/2 Here, the low is 0 and the high is 7. mid = (0+7)/2 mid = 3 (Integer)
Şimdi aranan elemanı orta indeks değeriyle karşılaştıracağız. Bu durumda, 32 eşit değildir Dört beş. Bu yüzden elementi bulmak için daha fazla karşılaştırma yapmamız gerekiyor.
Aradığımız sayının ortası eşitse. Sonra geri dön orta aksi takdirde daha sonraki karşılaştırmaya geçin.
Aranacak sayı şu sayıdan büyük: orta sayısını karşılaştırıyoruz N elemanların orta elemanı sağ tarafta olacak şekilde orta ve düşük seviyeye ayarlayın düşük = orta + 1.
Aksi halde karşılaştırın N ile orta eleman sol taraftaki elemanların orta ve ayarla yüksek ile yüksek = orta - 1.
Aradığımız numara bulunana kadar işlemi tekrarlayın.
Python'da İkili Arama Uygulama
İlk olarak yinelemeli yöntemle ikili arama gerçekleştiriyoruz. Bir dizi ifadeyi tekrarlayacağız ve listedeki her öğeyi yineleyeceğiz. Arama tamamlanana kadar ortadaki değeri bulacağız.
Yinelemeli yöntemin aşağıdaki programını anlayalım.
arayüz nedir
Python Uygulaması
# Iterative Binary Search Function method Python Implementation # It returns index of n in given list1 if present, # else returns -1 def binary_search(list1, n): low = 0 high = len(list1) - 1 mid = 0 while low <= 1 2 high: # for get integer result mid="(high" + low) check if n is present at list1[mid] n: high="mid" - smaller, compared to the left of else: return element was not in list, -1 initial list1 24, 32, 39, 45, 50, 54] function call n) !="-1:" print('element index', str(result)) list1') < pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 4 </pre> <p> <strong>Explanation:</strong> </p> <p>In the above program -</p> <ul> <li>We have created a function called <strong>binary_search()</strong> function which takes two arguments - a list to sorted and a number to be searched.</li> <li>We have declared two variables to store the lowest and highest values in the list. The low is assigned initial value to 0, <strong>high</strong> to <strong>len(list1)</strong> - 1 and mid as 0.</li> <li>Next, we have declared the <strong>while</strong> loop with the condition that the <strong>lowest</strong> is equal and smaller than the <strong>highest</strong> The while loop will iterate if the number has not been found yet.</li> <li>In the while loop, we find the mid value and compare the index value to the number we are searching for.</li> <li>If the value of the mid-index is smaller than <strong>n</strong> , we increase the mid value by 1 and assign it to The search moves to the left side.</li> <li>Otherwise, decrease the mid value and assign it to the <strong>high</strong> . The search moves to the right side.</li> <li>If the n is equal to the mid value then return <strong>mid</strong> .</li> <li>This will happen until the <strong>low</strong> is equal and smaller than the <strong>high</strong> .</li> <li>If we reach at the end of the function, then the element is not present in the list. We return -1 to the calling function.</li> </ul> <p>Let's understand the recursive method of binary search.</p> <h2>Recursive Binary Search</h2> <p>The recursion method can be used in the binary search. In this, we will define a recursive function that keeps calling itself until it meets the condition.</p> <p>Let's understand the above program using the recursive function.</p> <h3>Python Program</h3> <pre> # Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1') </pre> <p> <strong>Output:</strong> </p> <pre> Element is present at index 2 </pre> <p> <strong>Explanation</strong> </p> <p>The above program is similar to the previous program. We declared a recursive function and its base condition. The condition is the lowest value is smaller or equal to the highest value.</p> <ul> <li>We calculate the middle number as in the last program.</li> <li>We have used the <strong>if</strong> statement to proceed with the binary search.</li> <li>If the middle value equal to the number that we are looking for, the middle value is returned.</li> <li>If the middle value is less than the value, we are looking then our recursive function <strong>binary_search()</strong> again and increase the mid value by one and assign to low.</li> <li>If the middle value is greater than the value we are looking then our recursive function <strong>binary_search()</strong> again and decrease the mid value by one and assign it to low.</li> </ul> <p>In the last part, we have written our main program. It is the same as the previous program, but the only difference is that we have passed two parameters in the <strong>binary_search()</strong> function.</p> <p>This is because we can't assign the initial values to the low, high and mid in the recursive function. Every time the recursive is called the value will be reset for those variables. That will give the wrong result.</p> <h2>Complexity</h2> <p>The complexity of the binary search algorithm is <strong>O(1)</strong> for the best case. This happen if the element that element we are looking find in the first comparison. The <strong>O(logn)</strong> is the worst and the average case complexity of the binary search. This depends upon the number of searches are conducted to find the element that we are looking for.</p> <h2>Conclusion</h2> <p>A binary search algorithm is the most efficient and fast way to search an element in the list. It skips the unnecessary comparison. As the name suggests, the search is divided into two parts. It focuses on the side of list, which is close to the number that we are searching.</p> <p>We have discussed both methods to find the index position of the given number.</p> <hr></=> Açıklama:
Yukarıdaki programda -
- adında bir fonksiyon yarattık. Ikili arama() iki argüman alan işlev - sıralanacak bir liste ve aranacak bir sayı.
- Listedeki en düşük ve en yüksek değerleri saklamak için iki değişken tanımladık. Düşük olana başlangıç değeri 0 olarak atanır, yüksek ile uzun(liste1) - 1 ve ortası 0.
- Daha sonra, şunu ilan ettik: sırasında şu şartla döngü en düşük eşit ve daha küçüktür en yüksek Sayı henüz bulunamadıysa while döngüsü yinelenecektir.
- While döngüsünde ortadaki değeri bulup indeks değerini aradığımız sayıyla karşılaştırıyoruz.
- Orta endeksin değeri şundan küçükse: N orta değeri 1 arttırıp atadık. Arama sol tarafa doğru hareket eder.
- Aksi halde orta değeri azaltın ve bunu yüksek . Arama sağ tarafa doğru ilerler.
- Eğer n orta değere eşitse geri dön orta .
- Bu şu ana kadar gerçekleşecek Düşük eşit ve daha küçüktür yüksek .
- Fonksiyonun sonuna geldiğimizde eleman listede yok demektir. Çağıran fonksiyona -1 değerini döndürüyoruz.
İkili aramanın özyinelemeli yöntemini anlayalım.
Özyinelemeli İkili Arama
Özyineleme yöntemi ikili aramada kullanılabilir. Burada koşulu karşılayana kadar kendini çağırmaya devam eden özyinelemeli bir fonksiyon tanımlayacağız.
Yukarıdaki programı yinelemeli işlevi kullanarak anlayalım.
Python Programı
# Python program for recursive binary search. # Returns index position of n in list1 if present, otherwise -1 def binary_search(list1, low, high, n): # Check base case for the recursive function if low n: return binary_search(list1, low, mid - 1, n) # Else the search moves to the right sublist1 else: return binary_search(list1, mid + 1, high, n) else: # Element is not available in the list1 return -1 # Test list1ay list1 = [12, 24, 32, 39, 45, 50, 54] n = 32 # Function call res = binary_search(list1, 0, len(list1)-1, n) if res != -1: print('Element is present at index', str(res)) else: print('Element is not present in list1')
Çıktı:
Element is present at index 2
Açıklama
Yukarıdaki program önceki programa benzer. Özyinelemeli bir fonksiyon ve onun temel koşulunu bildirdik. Koşul, en düşük değerin en yüksek değerden küçük veya eşit olmasıdır.
- Ortadaki sayıyı son programdaki gibi hesaplıyoruz.
- Biz kullandık eğer ikili aramaya devam etmek için ifade.
- Ortadaki değer aradığımız sayıya eşitse ortadaki değer döndürülür.
- Ortadaki değer değerden küçükse özyinelemeli fonksiyonumuza bakıyoruz Ikili arama() tekrar orta değeri bir artırın ve düşüğe atayın.
- Ortadaki değer aradığımız değerden büyükse özyinelemeli fonksiyonumuz Ikili arama() tekrar orta değeri bir azaltıp düşük olarak atayın.
Son bölümde ana programımızı yazdık. Önceki programın aynısı ama tek farkı programda iki parametreyi geçmiş olmamız. Ikili arama() işlev.
Bunun nedeni özyinelemeli fonksiyonda başlangıç değerlerini düşük, yüksek ve orta değerlere atayamamamızdır. Özyinelemeli her çağrıldığında bu değişkenler için değer sıfırlanacaktır. Bu yanlış sonuç verecektir.
Karmaşıklık
İkili arama algoritmasının karmaşıklığı Ç(1) en iyi durum için. Bu, aradığımız öğenin ilk karşılaştırmada bulunması durumunda gerçekleşir. O(giriş) ikili aramanın en kötü ve ortalama durum karmaşıklığıdır. Bu, aradığımız öğeyi bulmak için yapılan arama sayısına bağlıdır.
klavyede f5 nedir
Çözüm
İkili arama algoritması, listedeki bir öğeyi aramanın en etkili ve hızlı yoludur. Gereksiz karşılaştırmayı atlıyor. Adından da anlaşılacağı gibi arama iki bölüme ayrılmıştır. Listenin aradığımız numaraya yakın olan tarafına odaklanır.
Verilen sayının indeks konumunu bulmak için her iki yöntemi de tartıştık.