Pengertian, Perbedaan Linear dan Binary Searching, dan Contoh Program C++

Searching atau pencarian dalam pemrograman merupakan metode untuk mencari item atau grup dari item di dalam koleksi suatu item. Tujuan dari searching yaitu untuk menemukan posisi dari item yang dicari sehingga dapat digunakan sesuai dengan kebutuhan.

Contoh dari searching yaitu misalnya kita memiliki sekumpulan data nomor sepatu, kemudian kita ingin mencari data nomor sepatu 38. Maka data akan dicari kemudian jika proses pencarian makan posisi dari item yang dicari akan ketemu.

Mari kita buat contoh programnya..

Tapi sebelum itu, kita perlu mengetahui macam-macam metode searching. Untuk metode searching yang sering digunakan yaitu metode linear dan biner. Mari kita bahas satu persatu.

Linear Searching

Linear searching biasanya disebut juga dengan sequential searching yang merupakan metode searching yang sederhana di mana setiap item dalam koleksi data diperiksa secara berurutan hingga ditemukan item yang dicari. Dalam linear searching, tidak ada syarat khusus pada data yang akan dicari atau urutan item dalam koleksi. 

Berbeda halnya dengan Binary Searching yang memiliki beberapa syarat agar proses searching dapat dilakukan

Binary Searching

Binary Searching merupakan metode pencarian yang digunakan untuk mencari item tertentu dalam koleksi data yang sudah terurut. Metode ini membagi koleksi data menjadi dua bagian secara berulang menggunakan pendekatan "bagi dua" (divide and conquer) untuk mempersempit ruang pencarian.

Jadi pada intinya, datanya harus sudah terurut kemudian bagi menjadi dua bagian, kemudian data dicari sampai data ditemukan.

Berarti apa saja yang membedakan Linear Searching dan Binary Searching?

Perbedaan Linear dan Binary Searching

Linear Search	Binary Search
Pencarian dilakukan secara berurutan, dengan memeriksa setiap elemen dari awal hingga akhir koleksi data.	Pencarian dilakukan dengan membagi koleksi data menjadi dua bagian secara berulang dan memeriksa elemen tengah untuk mempersempit ruang pencarian.
Bisa digunakan pada koleksi data yang terurut atau tidak terurut.	Hanya dapat digunakan pada koleksi data yang sudah terurut dalam urutan naik (ascending) atau urutan turun (descending).
Pencarian linier memerlukan waktu yang sebanding dengan jumlah elemen dalam koleksi data.	Pencarian biner lebih efisien karena memperkecil jumlah langkah yang dibutuhkan untuk mencari elemen.
Cocok digunakan untuk koleksi data yang kecil atau ketika tidak memungkinkan untuk melakukan pengurutan pada data.	Lebih cocok digunakan untuk koleksi data yang besar dan terurut, di mana efisiensi pencarian menjadi penting.

Masih ingat dengan contoh pencarian nomor sepatu? sekarang, mari kita buat contoh programnya.

Contoh Program Pencarian Nomor Sepatu dengan Linear Search

	#include <iostream>
	using namespace std;
	// fungsi linearSearch untuk melakukan pencarian menggunakan metode linear search
	// input: arr - array yang akan dicari, n - jumlah elemen dalam array, key - elemen yang dicari
	// output: Indeks elemen jika ditemukan, -1 jika tidak ditemukan
	int linearSearch(int arr[], int n, int key) {
	for (int i = 0; i < n; i++) {
	if (arr[i] == key) {
	return i; // jika elemen ditemukan, mengembalikan indeks
	}
	}
	return -1; // jika elemen tidak ditemukan, mengembalikan -1
	}
	int main() {
	// array data nosepatu
	int shoeSizes[] = { 39, 41, 37, 40, 38, 42, 36 };
	// ukuran array data nosepatu
	int n = sizeof(shoeSizes) / sizeof(shoeSizes[0]);
	// variabel utk input nosepatu yg akan dicari
	int searchSize;
	cout << "Masukkan nomor sepatu yang ingin dicari: ";
	cin >> searchSize;
	// inisialisasi variabel index dengan memanggil fungsi linear search dengan parameter yang sudah didefinisikan
	int index = linearSearch(shoeSizes, n, searchSize);
	// jika index bukan -1 (artinya ditemukan) maka akan menampilkan nosepatu yg dicari berada pd index ke berapa
	if (index != -1) {
	cout << "Nomor sepatu ditemukan pada indeks: " << index << endl;
	}
	// jika index -1 maka nosepatu tdk ditemukan alias datanya tidak ada
	else {
	cout << "Nomor sepatu tidak ditemukan" << endl;
	}
	return 0;
	}

view raw cariNoSepatuLinear.cpp hosted with ❤ by GitHub

Contoh Program Pencarian Nomor Sepatu dengan Binary Search

	#include <iostream>
	using namespace std;
	// fungsi binarySearch untuk melakukan pencarian menggunakan metode binary search
	// Input: arr - array yang akan dicari, low - batas bawah pencarian, high - batas atas pencarian, key - elemen yang dicari
	// Output: Indeks elemen jika ditemukan, -1 jika tidak ditemukan
	int binarySearch(int arr[], int low, int high, int key) {
	while (low <= high) {
	int mid = low + (high - low) / 2; // Menentukan indeks tengah
	if (arr[mid] == key) {
	return mid; // jika elemen ditemukan, mengembalikan indeks
	}
	else if (arr[mid] < key) {
	low = mid + 1; // jika elemen tengah lebih kecil dari elemen yang dicari, pencarian dilakukan pada separuh kanan array
	}
	else {
	high = mid - 1; // jika elemen tengah lebih besar dari elemen yang dicari, pencarian dilakukan pada separuh kiri array
	}
	}
	return -1; // Jika elemen tidak ditemukan, mengembalikan -1
	}
	int main() {
	int shoeSizes[] = { 36, 37, 38, 39, 40, 41, 42 };
	int n = sizeof(shoeSizes) / sizeof(shoeSizes[0]);
	int searchSize;
	cout << "Masukkan nomor sepatu yang ingin dicari: ";
	cin >> searchSize;
	int index = binarySearch(shoeSizes, 0, n - 1, searchSize);
	if (index != -1) {
	cout << "Nomor sepatu ditemukan pada indeks: " << index << endl;
	}
	else {
	cout << "Nomor sepatu tidak ditemukan" << endl;
	}
	return 0;
	}

view raw cariNoSepatuBiner.cpp hosted with ❤ by GitHub

Begitulah searching.....

Terimakasih

⸂⸂⸜(രᴗര๑)⸝⸃⸃..........