Mempelajari Tentang Algoritma Pencarian Biner Beserta Contoh
Algoritma pencarian biner adalah salah satu dari sekian banyak algoritma pengurutan yang digunakan dalam praktiknya. Mari kita cari tahu algoritma pencarian ini bersama-sama.
Untuk algoritma pengurutan, Anda dapat membaca lebih lanjut di: rangkaian algoritma pengurutan
Berikut adalah kode C / C ++ yang menggunakan pencarian linier.
Pertimbangkan array arr [kiri… kanan] perlu mencari elemen x. Kami membandingkan x dengan elemen di tengah array (mid = (kiri + kanan) / 2). Jika
Jika arr [mid] <xLakukan pencarian hanya di arr [mid + 1… right].
Bandingkan algoritma pencarian biner dan pencarian linierDengan menerapkan algoritma pencarian biner, kompleksitas kasus terburuk adalah O (log (n)).
Pencarian merupakan bagian integral dari setiap aplikasi, situs web, atau perangkat lunak. Fitur pencarian memungkinkan pengguna untuk menanyakan dan mencari catatan dengan cepat sesuai keinginan. Dan mesin pencari paling terkenal yang kami gunakan setiap hari adalah pencarian Google.
Artikel hari ini saya akan memperkenalkan pembaca pada algoritma pencarian yang optimal untuk data numerik yang diurutkan.
Pernyataan algoritma pencarian biner
Untuk array yang diurutkan arr [] dengan n elemen, tulis fungsi pencarian yang mengembalikan indeks elemen dengan nilai x dalam arr []. Algoritme paling sederhana untuk masalah ini adalah dengan menggunakan pencarian linier. Artinya, Anda harus melalui setiap elemen larik untuk dibandingkan dengan x. Algoritma ini dalam kasus terburuk untuk kompleksitas adalah O (n). Saya juga akan mengilustrasikan kode algoritma ini di bawah.
// Code from https://www.rurygans.eu.org
#include
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
// Returns the index when found
return i;
// If no match is found, -1 is returned. Because of the array index>= 0
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = search(arr, n, x);
if (result != -1) {
printf("%d appears in tai chi %d", x, result);
} else {
printf("%d not in bearing", x);
}
return 0;
} Karena sifat array yang diurutkan, pencarian elemen x dapat dilaksanakan sebagai berikut:
Jika elemen arr [mid] = x. Akhiri dan keluar dari program.
Jika arr [mid]> x. Lakukan pencarian hanya di arr [left… mid-1].
Gambar di bawah ini mensimulasikan implementasi algoritma pencarian biner dan membandingkannya dengan algoritma pencarian linier. Bandingkan algoritma pencarian biner dan pencarian linierDengan menerapkan algoritma pencarian biner, kompleksitas kasus terburuk adalah O (log (n)). Untuk Anda: Setelah pelajaran ini, Anda dapat menerapkan pengetahuan Anda tentang pencarian biner ke latihan praktik dalam Kode Praktik .
Demonstrasi kode untuk algoritma pencarian biner
Pada bagian ini, saya akan mendemonstrasikan kode menggunakan algoritma rekursif menggunakan Java dan C / C ++. Juga, saya akan menerapkan algoritma reduksi rekursif dengan C / C ++.
Kode menggambarkan C / C ++ menggunakan rekursi
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Code from https://nguyenvanhieu.vn
#include
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn
// Nếu arr[mid] = x, trả về chỉ số và kết thúc.
if (arr[mid] == x)
return mid;
// Nếu arr[mid] > x, thực hiện tìm kiếm nửa trái của mảng
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Nếu arr[mid] < x, thực hiện tìm kiếm nửa phải của mảng
return binarySearch(arr, mid + 1, r, x);
}
// Nếu không tìm thấy
return -1;
}
int main(void) {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
if (result == -1)
printf("%d xuat hien tai chi so %d", x, result);
else
printf("%d xuat hien tai chi so %d", x, result);
return 0;
} // Code from https://nguyenvanhieu.vn
class BinarySearch {
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
// Nếu arr[mid] = x, trả về chỉ số và kết thúc
if (arr[mid] == x)
return mid;
// Nếu arr[mid] > x, gọi đệ quy tìm kiếm bên trái
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Ngược lại, nếu arr[mid] < x, gọi đệ quy tìm kiếm bên phải
return binarySearch(arr, mid + 1, r, x);
}
// Trong trường hợp không tìm thấy
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {2, 3, 4, 10, 40};
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Không tìm thấy phần tử " + x);
else
System.out.println("Phần tử " + x + " được tìm thấy tại chỉ số " +
result);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// Code from https://nguyenvanhieu.vn
#include
// Hàm tìm kiếm nhị phân sử dụng giải thuật đệ quy
int binarySearch(int arr[], int n, int x) {
int r = n - 1; // chỉ số phần tử cuối
int l = 0; // Chỉ số phần tử đầu tiên
while (r >= l) {
int mid = l + (r - l) / 2; // Tương đương (l+r)/2 nhưng ưu điểm tránh tràn số khi l,r lớn
// Nếu arr[mid] = x, trả về chỉ số và kết thúc.
if (arr[mid] == x)
return mid;
// Nếu arr[mid] > x, cập nhật lại right
if (arr[mid] > x)
r = mid - 1;
// Nếu arr[mid] < x, cập nhật lại left
if (arr[mid] < x)
l = mid + 1;
}
// Nếu không tìm thấy
return -1;
}
int main(void) {
int arr[] = {
2,
3,
4,
10,
40
};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, n, x);
if (result == -1)
printf("%d xuat hien tai chi so %d", x, result);
else
printf("%d xuat hien tai chi so %d", x, result);
return 0;
}
