Salah satu algoritma yang paling mendasar dalam ilmu komputer adalah algoritma Binary Search. Anda dapat mengimplementasikan Pencarian Biner menggunakan dua metode: metode berulang dan metode rekursif. Meskipun kedua metode tersebut memiliki kompleksitas waktu yang sama, metode iteratif jauh lebih efisien dalam hal kompleksitas ruang.

Metode iteratif memiliki kompleksitas ruang sebesar O(1) jika dibandingkan dengan O(masuk) dihasilkan dengan metode rekursif. Jadi, bagaimana Anda bisa mengimplementasikan algoritma Binary Search menggunakan metode iteratif di C, C++, dan Python?

Apa itu Pencarian Biner?

Pencarian biner juga dikenal sebagai pencarian setengah interval, pencarian logaritmik, atau pemotongan biner adalah algoritma yang mencari dan mengembalikan posisi elemen dalam array yang diurutkan. Elemen pencarian dibandingkan dengan elemen tengah. Mengambil rata-rata batas bawah dan atas, Anda dapat menemukan elemen tengah.

Jika elemen pencarian lebih besar dari elemen tengah, berarti semua elemen di sisi kiri lebih kecil dari elemen pencarian. Jadi, kontrol bergeser ke sisi kanan array (jika array dalam urutan menaik) dengan menaikkan batas bawah ke posisi selanjutnya dari elemen tengah.

instagram viewer

Demikian pula, jika elemen pencarian lebih kecil dari elemen tengah, berarti semua elemen di sisi kanan lebih besar dari elemen pencarian. Jadi, kontrol bergeser ke bagian kiri array dengan mengubah batas atas ke posisi elemen tengah sebelumnya.

Ini mengurangi jumlah perbandingan secara drastis dibandingkan dengan implementasi pencarian linier di mana jumlah perbandingan sama dengan jumlah elemen dalam skenario terburuk. Metode ini terbukti sangat berguna untuk mencari nomor di buku telepon atau kata-kata di kamus.

Berikut adalah representasi diagram dari Algoritma Pencarian Biner:

Pencarian Biner Menggunakan C

Ikuti langkah-langkah berikut untuk mengimplementasikan Binary Search menggunakan C:

Seluruh kode sumber Program Pencarian Biner menggunakan C, C++, Java, dan Python hadir di sini repositori GitHub.

Program mendefinisikan fungsi, binarySearch(), yang mengembalikan indeks dari nilai yang ditemukan atau -1 jika tidak ada:

#termasuk <stdio.h>
intbinarySearch(int arr[], int arr_size, int search_number){
/*... */
}

Fungsi ini bekerja dengan mempersempit ruang pencarian secara iteratif. Karena pencarian biner berfungsi pada array yang diurutkan, Anda dapat menghitung bagian tengah yang tidak masuk akal. Anda dapat meminta array yang diurutkan kepada pengguna atau menggunakan algoritme pengurutan seperti Bubble atau Seleksi.

Itu rendah Dan tinggi variabel menyimpan indeks yang mewakili batas ruang pencarian saat ini. pertengahan menyimpan indeks di tengah:

int rendah = 0, tinggi = arr_size - 1, pertengahan;

Utama ketika() loop akan mempersempit ruang pencarian. Jika nilai indeks rendah menjadi lebih besar dari indeks tinggi, maka ruang pencarian telah habis, sehingga nilainya tidak dapat ditampilkan.

ketika (rendah <= tinggi) {
/* terus... [1] */
 }
kembali-1;

Setelah memperbarui titik tengah di awal putaran, ada tiga kemungkinan hasil:

  1. Jika nilai di titik tengah adalah yang kita cari, kembalikan index.
  2. Jika nilai titik tengah lebih besar dari yang kita cari, kurangi tinggi.
  3. Jika nilai titik tengahnya kurang, tingkatkan rendahnya. 
/* [1] ...lanjutan */
 pertengahan = (rendah + (tinggi - rendah)) / 2;
if (arr[mid] == search_number)
kembali pertengahan;
kalau tidakjika (arr[mid] > search_number)
 tinggi = pertengahan - 1;
kalau tidak
 rendah = pertengahan + 1;

Uji fungsi dengan input pengguna. Menggunakan scanf() untuk mendapatkan masukan dari baris perintah, termasuk ukuran larik, kontennya, dan angka untuk dicari:

intutama(){
int arr[100], i, ukuran_arr, nomor_pencarian;
 printf("Masukkan jumlah elemen: ");
 scanf("%D", &arr_size);
 printf("Silakan masukkan nomor: ");
untuk (i = 0; Saya < arr_size; saya++) {
 scanf("%D", &arr[i]);
 }


printf("Masukkan nomor yang akan dicari: ");
 scanf("%D", &nomor_pencarian);


i = binarySearch (arr, arr_size, search_number);


jika (i==-1)
 printf("Nomor tidak ada");
kalau tidak
 printf("Nomor hadir di posisi %d", i + 1);
kembali0;
}

Jika Anda menemukan nomornya, tampilkan posisi atau indeksnya, jika tidak, pesan yang mengatakan bahwa nomor tersebut tidak ada.

Pencarian Biner Menggunakan C++

Anda dapat mengonversi program C ke program C++ dengan mengimpor Arus Masukan Keluaran Dan gunakan namespace std untuk menghindari pengulangan beberapa kali sepanjang program.

#termasuk <iostream>
menggunakan ruang namastd;

Menggunakan cout dengan operator ekstraksi << alih-alih printf() Dan cin dengan operator penyisipan >> alih-alih scanf() dan program C++ Anda sudah siap.

printf("Masukkan jumlah elemen: ");
cout <<"Masukkan jumlah elemen: ";
scanf("%D", &arr_size);
cin >> arr_size;

Pencarian Biner Menggunakan Python

Karena Python tidak memiliki dukungan bawaan untuk array, gunakan daftar. Tentukan fungsi, binarySearch(), yang menerima tiga parameter, daftar, ukurannya, dan angka untuk dicari:

defbinarySearch(arr, ukuran_arr, nomor_pencarian):
 rendah = 0
 tinggi = arr_size - 1
ketika rendah <= tinggi:
 pertengahan = rendah + (tinggi-rendah)//2
 jika arr[mid] == nomor_pencarian:
kembali pertengahan
elif arr[mid] > nomor_pencarian:
 tinggi = sedang - 1
kalau tidak:
 rendah = sedang + 1
kembali-1

Inisialisasi dua variabel, rendah Dan tinggi, untuk berfungsi sebagai batas bawah dan atas daftar. Mirip dengan implementasi C, gunakan a ketika lingkaran yang mempersempit ruang pencarian. Inisialisasi pertengahan untuk menyimpan nilai tengah daftar. Python menyediakan operator divisi lantai (//) yang menyediakan bilangan bulat terbesar yang mungkin.

Buat perbandingan dan persempit ruang pencarian hingga nilai tengah sama dengan angka pencarian. Jika nomor pencarian tidak ada, kontrol akan kembali -1.

arr_size = int (input("Masukkan jumlah elemen: "))
arr=[]
mencetak("Silakan masukkan nomor: ", akhir="")
untuk saya dalam rentang (0,arr_size):
 arr.tambahkan(int(memasukkan()))
angka_pencarian = int (input("Masukkan nomor yang akan dicari: "))
hasil = binarySearch (arr, arr_size, search_number)
jika hasilnya == -1:
 mencetak("Nomor tidak ada")
kalau tidak:
 print("Nomor adalah hadir di posisi ", (hasil + 1))

Uji fungsi dengan input pengguna. Menggunakan memasukkan() untuk mendapatkan ukuran daftar, isinya, dan nomor untuk dicari. Menggunakan int() untuk mengetik masukan string yang diterima oleh Python sebagai default ke dalam bilangan bulat. Untuk menambahkan nomor ke daftar, gunakan menambahkan() fungsi.

Panggilan binarySearch() dan menyampaikan argumen. Jika Anda menemukan nomornya, tampilkan posisi atau indeksnya, jika tidak, pesan yang mengatakan bahwa nomor tersebut tidak ada.

Keluaran Algoritma Pencarian Biner

Berikut adalah output dari algoritma Binary Search ketika elemen tersebut ada di dalam array:

Berikut adalah output dari algoritma Binary Search ketika elemen tidak ada di dalam array:

Pelajari Struktur dan Algoritma Data Dasar

Pencarian adalah salah satu algoritme pertama yang Anda pelajari dan sering ditanyakan dalam kontes coding, penempatan, dan wawancara. Beberapa algoritma lain yang harus Anda pelajari adalah algoritma sorting, hashing, dynamic programming, string matching, dan primality testing.

Selain itu, penting untuk memahami kompleksitas waktu dan ruang dari algoritma. Mereka adalah salah satu konsep terpenting dalam Ilmu Komputer dalam menentukan efisiensi algoritma apa pun. Dengan pengetahuan tentang Struktur Data dan Algoritma, Anda pasti akan membuat program terbaik.