Thụât toán tìm kiếm nhị phân (Binary Search)

Trong bài đăng này chúng ta sẽ tìm hiểu về thuật toán tìm kiếm nhị phân (Binary search). Đây chính là thụât toán rộng rãi để tìm kiếm vị trí một phần tử trong một mảng đã bố trí.

Mục lục

Giải thuật tìm kiếm nhị phân (Binary Search) là gì ?

Binany Search (Tìm kiếm nhị phân) là một giải thuật tìm kiếm nhanh với độ phức tạp thời gian chạy là Ο(log n). Giải thuật tìm kiếm nhị phân làm việc dựa trên nguyên tắc chia để trị (Divide and Conquer). Để giải thuật này có thể làm việc một cách rõ ràng thì tập dữ liệu có thể ở trong dạng đã được sắp đặt.

Binary Search tìm kiếm một phần tử chi tiết bằng cách so sánh phần tử tại vị trí giữa nhất của tập dữ liệu. Nếu tìm thấy liên kết chặt chẽ thì chỉ mục của phần tử được trả về. Nếu như phần tử cần tìm là lớn hơn thành quả phần tử giữa thì phần tử cần tìm được tìm trong mảng con nằm ở bên phải phần tử giữa; nếu không thì sẽ tìm ở trong mảng con nằm ở bên trái phần tử giữa. Tiến trình sẽ lặp lại như vậy trên mảng con cho tới khi tìm hết mọi phần tử trên mảng con này.

1. Tìm kiếm nhị phân (Binary Search)

Thụât toán tìm kiếm nhị phân (Binary Search) hay còn được gọi là tìm kiếm một nửa là thụât toán tiếp kiếm được sử dụng cực kì nhiều trên thực tế cho phép tìm kiếm vị trí của một phần tử trong một mảng đã được sắp xếp.

Thụât toán tìm kiếm nhị phân thực hiện tìm kiếm một mảng đã bố trí bằng cách liên tục chia các khoảng tìm kiếm thành 1 nửa. Bắt đầu với một khoảng từ phần tử đầu mảng, tới cuối mảng. Nếu giá trị của phần tử cần tìm nhỏ hơn giá trị của phần từ nằm ở giữa khoảng thì thu hẹp phạm vi tìm kiếm từ đầu mảng tới giửa mảng và nguợc lại. Cứ thế tiếp tục chia phạm vi thành các nửa cho dến khi tìm thấy hoặc đã duyệt hết.

2. Ý tưởng thụât toán

Thuật toán tìm kiếm nhi phân là một thuật toán khá thông dụng và chỉ dùng được với một mảng đã sắp đặt. Để khai triển thuật toán này hãy chắc chắn rằng mảng đã được bố trí. Sau đây là cảm hứng khai triển thuật toán.

Xét một đoạn trong mảng arr[left…right]. Lúc này thành quả của left và right lần luợt là 0 và số phần tử của mảng - 1.
So sánh x với phần tử nằm ở vị trí chủ đạo giữa của mảng (mid = (left + right) /2). Nếu như x bằng arr[mid] thì trả về vị trí và thoát vòng lặp.
Nếu như x < arr[mid] thì chắc chắn x sẽ nằm ở phía bên trái tức là từ arr[left….mid-1].
Nếu như x > arr[mid] thì chắc chắn x sẽ nằm ở phía bên phải mid tức là ở khoảng arr[mid+1…right].
Bắt đầu hành động chia đôi các khoảng tìm kiếm tới khi nào tìm thấy được vị trí của x trong mảng hoặc khi đã duyệt hết mảng.

3. Triển khai thụât toán

Sau đây chính là các bước khai triển thuật toán, quá trình hành động đều được bình luận ở từng đoạn.

1
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

#include 
using namespace std;
//Hàm tìm kiếm nhi phân
int binarySearch(int arr[], int left, int right, int x) 
int middle;
while(left <= right) 
// tính vị trí ở giữa left và right
middle = (left + right) / 2;
// nếu phần từ ở giữa bằng x thì trả về
// vị trí
if (arr[middle] == x)
return middle;
// nếu x lớn hơn phần tử ở giữa thì
// bảo đảm nó nằm bên phải.
// Chỉ định left phần từ ở giữa + 1
if (x > arr[middle])
left = middle + 1;
else
//Ngược lại
right = middle - 1;
//Trả về -1 nếu không tìm thấy gía trị trong mảng.
return -1;
int main() 
int arr[] = 15, 20, 25, 30, 31, 44, 66;
//Lấy ra độ dài của mảng
int n = sizeof(arr) / sizeof(arr[0]);
//Phần từ cần tìm
int x = 25;
// n -1 là vị trí cuối cùng trong mảng.
int result = binarySearch(arr, 0, n-1, x);
cout << result;

Khởi chạy chương trình chúng ta sẽ nhận được kết quả là vị trí của 25 trong mảng.

1

Output : 2

>>>Xem thêm: Mã nguồn mở là gì? Tổng hợp các mã nguồn mở tốt nhất hiện nay

Ý tưởng của thuật toán tìm kiếm nhị phân

Chú ý: Trong bài đăng tôi giả sử mảng đang sắp xếp tăng dần. Với trường hợp mảng sắp xếp giảm dần, bạn đọc sau khi hiểu thuật toán sẽ có thể tự làm.

Do tính chất mảng đã sắp xếp, quá trình tìm kiếm phần tử x có thể khai triển như sau:

Xét đoạn mảng arr[left…right] cần tìm kiếm phần tử x. Ta so sánh x với phần tử ở vị trí giữa của mảng(mid = (left + right)/2). Nếu:
Nếu như phần tử arr[mid] = x. Kết luận và thoát chương trình.
Nếu như arr[mid] < x. Chỉ tìm kiếm trên đoạn arr[mid+1…right].
Nếu arr[mid] > x. Chỉ tìm kiếm trên đoạn arr[left…mid-1].

>>>Xem thêm: Những phần mềm viết Code tốt nhất cho lập trình viên hiện nay

Tóm lại

Trên đây là phần giới thiệu cũng như triển khai của thụât toán tìm kiếm nhị phân. Đây cũng là một thuật toán hay được sử dụng cũng như rât có ích trong quá trình giải các bài toán tìm kiếm.

Bài viết trên, mình đã chia sẻ tới các bạn những nội dung thiết yếu của tìm kiếm nhị phân. Cảm ơn các bạn đã theo dõi bài viết nhé!