ikili arama Pythonu

Python işlevleri ve meth

Bir Python ikili araması, sıralanmış bir dizideki bir öğenin konumunu bulur. Bir listeyi ikiye böler. Belirtilen değer ortadaki sayıdan büyükse, arama listenin sağına odaklanır. Aksi takdirde, arama listenin solundaki numarayı arar.

Listedeki bir öğenin konumunu nasıl bulursunuz? İkili aramalar bu konuda arkanızda. İkili aramaları kullanarak, sıralanmış bir dizi içindeki bir öğenin konumunu kolayca bulabilirsiniz.

Bilgisayarlar, belirli bir öğeyi bulmak için listeler arasında arama yapmakta iyidir. Bilgisayarların bir listedeki öğeleri bulmak için kullandığı kurallara arama algoritmaları denir. En popüler Python algoritmalarından biri ikili aramadır.

Bu kılavuzda, ikili aramaların ne olduğunu ve ikili aramaların neler olduğunu tartışacağız. onlar nasıl çalışır. Programlarınıza nasıl bir tane yazacağınızı öğrenebilmeniz için Python'da bir ikili arama örneğini inceleyeceğiz. Haydi başlayalım!




Python İkili Araması nedir?

Python ikili araması, sıralı bir dizideki bir öğenin konumunu bulan bir algoritmadır. İkili aramalar, bir listeyi tekrar tekrar ikiye böler. Ardından, bir değerin listedeki orta değerden daha yüksek veya daha düşük olup olmadığı bir aramayla karşılaştırılır.

İkili arama gerçekleştirmenin iki yolu vardır. Her iki yaklaşım da bir dizideki belirli bir noktada en yüksek ve en düşük konumları izlemek için kullanılan işaretçiler ayarlar.

Kullanabileceğiniz ilk yaklaşım yinelemeli yöntemdir. Bu yaklaşımda, bir dizideki bir elemanın konumunu belirlemek için bir dizi ifade tekrarlanır. Python'da bu amaçla bir while döngüsü kullanırız.

Diğer yaklaşım özyinelemeli yöntemdir. Burası, listedeki bir eleman bulunana kadar kendini tekrar tekrar çağıran bir fonksiyon yazdığınız yerdir. Özyinelemeli yöntem, daha önce tartıştığımız böl ve yönet yaklaşımını kullanır ve bir öğe bulunana kadar arama sürecini tekrarlar.

Katılımcıların %81'i, bir eğitim kampına katıldıktan sonra teknik iş beklentileri konusunda daha emin hissettiklerini belirtti. . Bugün bir eğitim kampı ile eşleştirin.

Ortalama bir eğitim kampı mezunu, bir eğitim kampına başlamaktan ilk işini bulmaya kadar, kariyer geçişinde altı aydan az zaman harcadı.

Bölünmeyle ilgili onca konuşmayla ve fetih ve özyineleme, bir ikili aramanın tam olarak nasıl çalıştığının izini kaybetmek kolay olabilir. Bu nedenle, ikili aramanın nasıl çalıştığına ilişkin doğrudan bir örneğe atlayacağız. Aşağıdaki listeyi göz önünde bulundurun:

79142234

“22” listemizde.

Başlamak için listelerimize iki işaretçi koyacağız. Bir işaretçi listedeki en yüksek değeri, diğer nokta ise en düşük değeri yansıtacaktır:

< /table>

Sonraki adımımız, dizinin ortasındaki 14 olan elemanı bulmaktır. Bu değer, aradığımız değere eşitse, bu değer döndürülmelidir.

Bu durumda 14, 22 ile aynı değildir. Dolayısıyla programımızın bir karşılaştırma yapması gerekiyor.


Aradığımız sayıyı, mevcut orta elemanın sağ tarafındaki elemanların orta elemanı ile karşılaştıracağız.Bunu ancak aradığımız sayı ise yapacağız. ortadaki sayıdan büyüktür. Aksi takdirde, öğeyi mevcut orta öğenin solundaki orta öğeyle karşılaştırırız.

22 sayısı 14'ten büyüktür. Programımız 22'yi karşılaştırmaya başlar. mevcut orta elemanımızın (14) sağ tarafındaki orta elemana. Bu durumda, bu sayı 22'dir. Bu, aradığımız sayıya eşittir.

Biz’ orta değer. Programımız şimdi o sayının dizin konumunu döndürecek. Bu durumda, 22'nin dizin konumu 3'tür (unutmayın, listeler 0'dan başlayarak dizine eklenir!).




İkili Nasıl Uygulanır? Python'da Ara

Haydi&rsq uo;s bazı Python kodları ile ellerimizi kirletir. Daha önce tartıştığımız yaklaşımların ikisini de kullanarak ikili aramanın Python uygulamasını keşfedeceğiz: yinelemeli ve özyinelemeli yöntemler.

Python'da Yinelemeli İkili Arama 

Biz’ yinelemeli yöntemle başlayacağım. Burası, listemizdeki her öğenin üzerinden geçeceğimiz yerdir. Ardından, listede ortadaki değeri bulacağız. Aradığımız değeri bulana kadar bunu yapmaya devam edeceğiz.

İkili Arama Fonksiyonu

Bir Python işlevi:

def findValue(numbers, number_to_find) : düşük = 0 yüksek = len(listnumbers - 1 iken düşük <= yüksek: orta = düşük + (yüksek - düşük) // 2 if sayılar[orta] == sayı_to_find: ortadaki elif sayılarını döndürür[orta] < sayı_to_find: düşük = orta + 1 başka: yüksek = orta - 1 dönüş -1 

Fonksiyonumuz iki parametre kabul eder: arama yapmak istediğimiz liste ve içinde bulmak istediğimiz sayı listemizde.

Ardından listedeki en düşük ve en yüksek değerler için varsayılan değerleri depolayan iki Python değişkeni bildirdik. < em>düşük, listedeki başlangıç ​​dizin değeri olan 0'a ayarlanır. yüksek, listenin uzunluğuna ayarlanır m inus one (çünkü listeler sıfırdan dizine eklenir).

Bir sonraki adımımız bir Python while döngüsü bildirmekti. Bu döngü, en düşük eleman en yüksek sayıdan küçük veya ona eşitken çalışır. Bu, döngümüzün ancak sayı henüz bulunamadığında çalışacağı anlamına gelir.

Ardından ortadaki sayıyı hesaplıyoruz. Bunu en yüksek değerden en düşük değeri çıkararak yaparız. Daha sonra o sayının 2'ye bölündüğünde modulosunu (kalanını) hesaplıyoruz. Ardından modulo'yu en küçük sayının değerine ekliyoruz.

Listemizde ortadaki sayı ile sayı aynı ise. bulmak istiyorsak, o sayının konumunu döndürürüz.

Yeni “düşük” sayı, orta konumdan bir büyük olmalıdır. Bu, ortadaki sayı bulmak istediğimiz sayıdan küçükse olur. Bu, daha önce görsel örneğimizde yaptığımız gibi aramamızı listemizin sol tarafına kaydırır.


Aksi takdirde, “yüksek” sayımızı orta konumdan bir eksik olacak şekilde ayarlarız. Bu, aramamızı listemizin sağ tarafına taşır.

" Python.Engineering hayatıma en çok ihtiyacım olduğu anda girdi ve hızlı bir şekilde bir bootcamp ile eşleşmeme yardımcı oldu. Mezun olduktan iki ay sonra, hayattaki değerlerim ve hedeflerime uygun hayalimdeki işi buldum!"

Venus, Rockbot'ta Yazılım Mühendisi

< p>Bu, low, high'a eşit veya daha düşük olana kadar tekrarlanır. Değerimiz bulunamazsa, -1 döndürürüz. Nedenini birazdan konuşacağız.

Aramayı Yürütün

Aşağıdaki kodu programınızın altına findValue işlevinin dışında ekleyin:

numbers = [7, 9, 14, 22, 34] number_to_find = 22 final = findValue(numbers, number_to_find) if final == -1: print("Bu öğe listede bulunamadı.") else: print(" " + str(number_to_find) + " sayısı " + str(final) + " dizin konumunda bulundu.") 

Listeyi bildirerek başladık Ardından, bulmak istediğimiz sayı olan 22'yi belirledik.

Sonra, findValue() fonksiyonumuzu a diyoruz. ve listeyi içinden geçirin.

-1'in daha önce geldiği yer burasıdır. Fonksiyonumuz tarafından döndürülen sayı -1 ise, öğemiz listede bulunamadı demektir. Arama fonksiyonumuz negatif bir sayı döndüremeyeceğinden, programcılar genellikle -1'i bu gibi durumlarda kullanır.

Aksi takdirde, programımız bize bu değerin dizin konumunu bildiren bir mesaj yazdırır.

< p>Kodumuz şunu döndürür:

22 sayısı dizin 3 konumunda bulundu.

Artık 22 sayısının dizin 3 konumunda göründüğünü biliyoruz.

Python'da Özyinelemeli İkili Arama

İkili arama yapmak için özyinelemeyi de kullanabiliriz. Burası, bir koşul – numaramız bulundu – karşılandı.

Bir Özyinelemeli İşlev Tanımlayın

Son örneğimizde olduğu gibi ikili aramamızı gerçekleştiren bir işlev yazarak başlayacağız:

def findValue(sayılar, sayı_bulunan sayı, düşük, yüksek): if yüksek >= düşük: orta = düşük + (yüksek - düşük) // 2 if sayılar[middle] == number_to_find: ortadaki elif sayılarını döndür[middle] < number_to_find: return findValue(numbers, number_to_find, orta + 1, yüksek) else: return findValue(numbers, number_to_find, düşük, orta - 1) else: return -1 

Kodumuz bir şekilde son örneğimize benzer.

En yüksek değerin düşükten büyük veya eşit olup olmadığını kontrol ederek başlıyoruz. Eğer öyleyse, programımız -1 döndürür. Aksi takdirde ikili arama yapmaya başlayacaktır.

Son örnekteki ile aynı yaklaşımı kullanarak ortadaki sayıyı hesaplıyoruz. İlk olarak, en düşük değeri en yüksek değerden çıkarıyoruz. Ardından, 2'ye bölündüğünde bu değerin modulosunu (kalanını) hesaplarız. Son olarak, en düşük sayıyı ekleriz.

Ardından, nasıl olacağına karar veren bir if ifadesi yazdık. ikili aramamız devam etmelidir:

  • Ortadaki sayı aradığımız sayıya eşitse, o sayının konumu döndürülür.
  • Ortadaki sayı ise aradığımızdan daha az, findValue() fonksiyonumuz tekrar çağrılır. Bu sefer düşük değeri ortadaki değerden bir büyük olacak şekilde ayarlanmıştır.
  • Ortadaki sayı aradığımızdan büyükse, < em>findValue() işlevi çağrılır. “yüksek” ortadaki değerden bir eksik olacaktır.

Ana Programı Yazın

Tek yapmamız gereken ana programımızı yazmak:

numbers = [7, 9, 14, 22, 34] number_to_find = 22 final = findValue(numbers, number_to_find, 0, len(sayılar) - 1) eğer final == - 1: print("Bu öğe listede bulunamadı.") else: print("Sayı " + str(number_to_find) + " dizin konumunda " + str(final) + ".") 

Ana programımız önceki örneğimizle aynı, bir fark var. findValue() işlevimize iki yeni parametre aktarıyoruz: düşük ve yüksek.

Algoritmamız özyinelemeli olduğundan ve bu değerleri fonksiyonumuzda atayamadığımız için bunu yapmamız gerekiyor. Eğer değerleri fonksiyonumuzda atasaydık, fonksiyonumuz her çalıştırıldığında bu değerler sıfırlanır, bu da arama algoritmamızı boz.

Kodumuz şunu döndürür:

22 sayısı şurada bulundu: dizin konumu 3.

Daha önce de aynı sonucu aldık. Bu örnekte, ikili aramamızı gerçekleştirmek için yinelemeli bir program yerine yinelemeli bir program kullandık.




Python İkili Aramasını Ne Zaman Kullanmalısınız?

İkili arama, bir bir numara listesinde arama yapmanın etkili yolu. Bu arama, doğrusal bir aramadan daha verimlidir. Bunun nedeni, ikili yöntemin, sıralanmış bir listenin ortasını bulur bulmaz aramanızı yarıya indirmesidir.

Bir listenin, kullanılarak aranabilmesi için önce sayısal olarak sıralanması gerektiğini unutmamak önemlidir. ikili arama İkili arama yapmadan önce, numaralarınızın artan düzende sıralandığından emin olun.




Python Karmaşıklık Dağılımı'nda İkili Arama

İkili aramanın karmaşıklığı nedir? Bu güzel bir soru.

İkili arama algoritmasının en iyi durum karmaşıklığı O(1)'dir. Bu, ilk karşılaştırma aradığınız öğeye eşit olduğunda gerçekleşir.

İkili arama için ortalama ve en kötü durum karmaşıklığı O(log n)'dir. Bu, bir arama yapmak için gereken sürenin, bir listede aranacak öğe sayısına bağlı olarak logaritmik olarak arttığı anlamına gelir.




Sonuç

İkili aramalar verimli bir yoldur. bir listedeki bir değerin dizin konumunu bulmak için.

İkili arama her çalıştırıldığında, arama listeyi iki parçaya böler. Arama, listenin aradığınız numaraya en yakın tarafına odaklanır.

Arama her çalıştırıldığında, programın araması gereken sayı miktarı yarıya düşer.

p>

Python hakkında daha fazla bilgi edinmek için Python Nasıl Öğrenilir kılavuzumuzu okuyun.





ikili arama Pythonu: StackOverflow Questions

Düşük


Yüksek
79142234