Pencarian Binari di Python: Pengenalan Visual

Pengaturcaraan

Selamat datang

Dalam artikel ini, anda akan belajar bagaimana algoritma Binary Search berfungsi di belakang tabir dan bagaimana anda dapat menerapkannya di Python.

Khususnya, anda akan belajar:

  • Bagaimana algoritma berfungsi di belakang tabir untuk mencari elemen sasaran.
  • Bagaimana pelaksanaan Pythonnya berjalan mengikut baris.
  • Mengapa ia adalah algoritma yang sangat efisien berbanding dengan Linear Search.
  • Kelebihan dan keperluannya.

Mari kita mulakan! ✨

? Pengenalan Carian Binari

Algoritma ini digunakan untuk mencari elemen dalam urutan teratur (contohnya: senarai, tuple, atau rentetan).

Keperluan

Untuk menggunakan algoritma Binary Search pada urutan, urutan sudah harus disusun mengikut urutan menaik. Jika tidak, algoritma tidak akan menemui jawapan yang betul. Sekiranya ia berlaku, ia akan berlaku secara kebetulan.

? Petua: Anda boleh menyusun urutan sebelum menggunakan Carian Binari dengan algoritma penyortiran yang memenuhi keperluan anda.

Input dan Keluaran

Algoritma (dilaksanakan sebagai fungsi) memerlukan data ini:

  • Urutan elemen yang disusun (contohnya: senarai, tuple, string).
  • Elemen sasaran yang kami cari.

Ia mengembalikan indeks elemen yang anda cari jika ia dijumpai. Sekiranya elemen tidak dijumpai, -1 dikembalikan.

Kecekapan

Ia sangat efisien berbanding dengan Carian Linear (mencari elemen satu persatu, bermula dari yang pertama) kerana kita dapat "membuang" separuh senarai pada setiap langkah.

Mari kita mulakan algoritma ini.

Through Laluan Visual

Kami akan menggunakan algoritma Pencarian Binari ke senarai ini:

? Petua: Perhatikan bahawa senarai sudah disusun. Ini memasukkan indeks sebagai rujukan visual.

Matlamat

Kami mahu mencari indeks bilangan bulat 67 .

Selang

Mari berpura-pura bahawa kita adalah algoritma. Bagaimana kita memulakan prosesnya?

Kita mulakan dengan memilih dua batas selang di mana kita mahu mencari. Kami ingin mencari keseluruhan senarai, jadi kami memilih indeks 0sebagai batas bawah dan indeks 5sebagai batas atas:

Elemen Tengah

Sekarang kita perlu mencari indeks elemen tengah dalam selang masa ini. Kami melakukan ini dengan menambahkan batas bawah dan batas atas dan membahagikan hasilnya dengan 2 menggunakan pembahagian integer.

Dalam kes ini, (0 + 5)//2adalah 2kerana hasil 5/2adalah 2.5dan pembahagian integer truncates sebahagian perpuluhan.

Jadi elemen tengah terletak di indeks 2 , dan elemen tengah adalah nombor 6 :

Perbandingan

Sekarang kita perlu mula membandingkan elemen tengah dengan elemen sasaran kita untuk melihat apa yang perlu kita lakukan seterusnya.

Kami tanya:

Adakah elemen tengah sama dengan elemen yang kita cari?

6 == 67 # False

Tidak, tidak.

Oleh itu, kami bertanya:

Adakah elemen tengah lebih besar daripada elemen yang kita cari?

6 > 67 # False

Tidak, tidak.

Jadi elemen tengah lebih kecil daripada elemen yang kita cari.

6 < 67 # True

Buang Elemen

Oleh kerana senarai itu sudah disusun, ini memberitahu kita sesuatu yang sangat penting. Ini memberitahu kita bahawa kita dapat "membuang" bahagian bawah senarai kerana kita tahu bahawa semua elemen yang datang sebelum elemen tengah akan lebih kecil daripada elemen yang kita cari, jadi elemen sasaran kita tidak ada.

Mulakan Lagi - Pilih Batasan

Apa yang akan kita buat seterusnya? Kami telah membuang unsur-unsur dan kitaran diulang lagi.

Kita harus memilih batasan untuk selang baru (lihat di bawah). Tetapi perhatikan bahawa batas atas tetap utuh dan hanya batas bawah yang diubah.

Ini kerana elemen yang kita cari mungkin ada di bahagian atas senarai. Batas atas tetap utuh dan batas bawah diubah menjadi "mengecilkan" selang menjadi selang di mana elemen sasaran kita dapat dijumpai.

? Petua: Sekiranya elemen tengah lebih besar daripada elemen yang kita cari, batas atas akan berubah dan batas bawah akan tetap utuh. Dengan cara ini, kami akan membuang separuh bahagian atas senarai dan terus mencari di bahagian bawah.

Elemen Tengah

Sekarang kita perlu mencari indeks elemen tengah dengan menambahkan batas bawah ke batas atas dan membahagi hasilnya dengan 2 menggunakan pembahagian integer.

Hasilnya (3+5)//2adalah 4, jadi elemen tengah terletak pada indeks4 dan elemen tengah adalah 67 .

Perbandingan

Kami tanya:

Adakah elemen tengah sama dengan elemen yang kita cari?

67 == 67 # True

Ya betul! Oleh itu, kami telah menemui elemen pada indeks 4 . Nilai 4 dikembalikan dan algoritma berjaya diselesaikan.

? Petua: Sekiranya elemen tidak dijumpai, prosesnya akan berlanjutan sehingga selang waktu itu tidak lagi berlaku. Sekiranya elemen tidak dijumpai dalam keseluruhan senarai, -1 akan dikembalikan.

? Penjelasan Kod

Setelah anda mempunyai intuisi visual bagaimana algoritma berfungsi di belakang tabir, mari kita selami pelaksanaan Python berulang dengan menganalisisnya mengikut baris:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

Kepala

Di sini kita mempunyai tajuk fungsi:

def binary_search(data, elem):

Ia memerlukan dua hujah:

  • Urutan elemen yang disusun (contohnya: senarai, tuple, atau rentetan).
  • Elemen yang ingin kita cari.

Selang Permulaan

Baris seterusnya menetapkan had awal dan bawah awal:

low = 0 high = len(data) - 1

Batas bawah awal adalah indeks 0dan batas atas awal adalah indeks terakhir urutan.

Gelung

Kami akan mengulangi proses sementara terdapat selang waktu yang sah, sementara batas bawah lebih kecil dari atau sama dengan batas atas. 

while low <= high:

? Petua: Ingat bahawa batas adalah indeks.

Elemen Tengah

Pada setiap lelaran, kita perlu mencari indeks elemen tengah. Untuk melakukan ini, kami menambah batas bawah dan atas dan membahagikan hasilnya dengan 2 menggunakan pembahagian integer.

middle = (low + high)//2

? Petua: Kami menggunakan pembahagian integer sekiranya senarai atau selang mengandungi bilangan elemen genap. Sebagai contoh, jika senarai itu mempunyai 6 elemen dan kita tidak menggunakan pembahagian integer, middlemaka hasilnya (0 + 5)/2adalah 2.5. Indeks tidak boleh menjadi apungan, jadi kami memangkas bahagian perpuluhan dengan menggunakan //dan memilih elemen pada indeks 2.

Perbandingan

Dengan syarat-syarat ini (lihat di bawah), kami menentukan apa yang harus dilakukan bergantung pada nilai elemen tengah data[middle]. Kami membandingkannya dengan elemen sasaran yang kami cari.

if data[middle] == elem: return middle elif data[middle] > elem: high = middle - 1 else: low = middle + 1

Terdapat tiga pilihan:

  • Sekiranya elemen tengah sama dengan elemen yang kita cari, kita segera mengembalikan indeks kerana kita menjumpai elemen tersebut.
if data[middle] == elem: return middle
  • Sekiranya elemen tengah lebih besar daripada elemen yang kita cari, kita menetapkan semula batas atas kerana kita tahu bahawa elemen sasaran berada di bahagian bawah senarai.
elif data[middle] > elem: high = middle - 1
  • Jika tidak, satu-satunya pilihan yang tinggal adalah elemen tengah lebih kecil daripada elemen yang kita cari, jadi kita menetapkan semula batas bawah kerana kita tahu bahawa elemen sasaran berada di bahagian atas senarai.
else: low = middle + 1

Elemen Tidak Dijumpai

Sekiranya gelung selesai tanpa mencari elemen, nilai -1 dikembalikan.

return -1

dan kami mempunyai pelaksanaan akhir algoritma Pencarian Binari:

def binary_search(data, elem): low = 0 high = len(data) - 1 while low  elem: high = middle - 1 else: low = middle + 1 return -1

? Kes Khas

Ini adalah beberapa kes tertentu yang mungkin anda dapati semasa anda mula menggunakan algoritma ini:

Elemen Berulang

Sekiranya elemen yang anda cari diulang mengikut urutan, indeks yang dikembalikan akan bergantung pada bilangan elemen dan pada urutan operasi yang dilakukan oleh algoritma pada urutan.

>>> >>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 7) 4

Elemen Tidak Dijumpai

Sekiranya elemen tidak dijumpai, -1 dikembalikan.

>>> b = [2, 2, 3, 6, 7, 7] >>> binary_search(b, 8) -1

Urutan Kosong

Sekiranya urutan kosong, -1 akan dikembalikan.

>>> b = [] >>> binary_search(b, 8) -1

Urutan yang tidak disusun

Sekiranya urutan tidak disusun, jawapannya tidak akan betul. Mendapatkan indeks yang betul adalah kebetulan semata-mata dan ia mungkin disebabkan oleh susunan elemen dalam urutan dan urutan operasi yang dilakukan oleh algoritma.

Contoh ini mengembalikan hasil yang betul:

>>> b = [5, 7, 3, 0, -9, 2, 6] >>> binary_search(b, 6) 6

Tetapi yang ini tidak:

>>> b = [5, 7, 3, 0, -9, 2, 10, 6] >>> binary_search(b, 6) -1

? Petua: Fikirkan mengapa contoh pertama mengembalikan hasil yang betul. Petunjuk: Kebetulan murni bahawa susunan elemen berlaku untuk membuat algoritma mencapai indeks yang betul, tetapi proses langkah demi langkah menilai 0, kemudian 2, dan akhirnya 6. Dalam kes ini, untuk elemen tertentu ini, indeks yang betul dijumpai walaupun urutan tidak disusun.

? Contoh Yang Lebih Kompleks

Sekarang anda lebih biasa dengan algoritma dan pelaksanaan Pythonnya, di sini kami mempunyai contoh yang lebih kompleks:

Kami ingin mencari indeks elemen 45 dalam senarai ini menggunakan Carian Binari:

Pengulangan Pertama

Batas bawah dan atas dipilih:

Elemen tengah ( 26 ) dipilih:

Tetapi elemen tengah ( 26 ) bukan elemen yang kita cari, ia lebih kecil daripada 45 :

Pengulangan Kedua

Oleh itu, kita boleh membuang semua elemen yang lebih kecil daripada elemen tengah dan memilih batas baru. Batas bawah baru ( 27 ) adalah elemen yang terletak betul-betul di sebelah kanan elemen tengah sebelumnya:

? Petua: Ingat bahawa senarai sudah disusun.

Elemen tengah baru ( 30 ) dipilih:

Elemen tengah ( 30 ) bukan elemen yang kita cari, lebih kecil daripada 45 :

Pengulangan Ketiga

Kita boleh membuang unsur-unsur yang lebih kecil daripada atau sama dengan 30 yang belum dibuang. Batas bawah dikemas kini kepada 32 :

Di sini kita mempunyai satu kes yang menarik: unsur tengah adalah salah satu batas selang semasa kerana (7+8)//2adalah 7.

Elemen tengah ( 32 ) bukan elemen yang kita cari ( 45 ), lebih kecil.

Pengulangan Keempat

Kita boleh membuang unsur-unsur yang lebih kecil daripada atau sama dengan 32 yang belum dibuang.

Di sini kita mempunyai satu lagi kes yang sangat menarik: selang hanya mempunyai satu elemen.

? Petua: Selang ini berlaku kerana kami menulis keadaan ini while high <= low:, yang merangkumi selang di mana indeks batas bawah sama dengan indeks batas atas.

Elemen pertengahan adalah satu-satunya elemen dalam selang kerana (8+8)//2adalah 8, jadi indeks unsur tengah adalah 8 dan elemen tengah 45 .

Sekarang elemen tengah adalah elemen yang kita cari, 45 :

Jadi nilai 8 (indeks) dikembalikan:

>>> binary_search([1, 3, 7, 15, 26, 27, 30, 32, 45], 45) 8

? Amalan Tambahan

Sekiranya anda ingin melakukan latihan tambahan dengan algoritma ini, cuba terangkan bagaimana algoritma berfungsi di belakang tabir ketika diterapkan ke senarai ini untuk mencari bilangan bulat 90 :

[5, 8, 15, 26, 38, 56]
  • Apa yang berlaku selangkah demi selangkah?
  • Nilai apa yang dikembalikan?
  • Adakah unsur itu dijumpai?

Saya sangat berharap anda menyukai artikel saya dan menganggapnya berguna. Sekarang anda boleh melaksanakan algoritma Binary Search di Python. Lihat kursus dalam talian saya "Python Search & Sorting Algorithms: A Practical Approach". Ikuti saya di Twitter. ⭐️