DANH SÁCH BÀI VIẾT Tìm hiểu thuật toán Quy hoạch động Tìm hiểu về Hàm đệ quy Thuật toán tìm kiếm nhị Tìm hiểu về Thuật toán quay lui (Backtracking) Tìm hiểu thuật toán Loang Tìm hiểu thuật toán chia để trị Tìm hiểu thuật toán tham lam trong lập trình Giải thuật tìm kiếm theo chiều sâu DFS (Depth First Search) Giải thuật tìm kiếm theo chiều rộng BFS (Breadth-first search) Tìm hiểu về thuật toán Sàng nguyên tố (sàng Eratosthenes)
Thuật toán tìm kiếm nhị phân là một trong các thuật toán tìm kiếm được sử dụng rất nhiều trong thực tế. Hãy cùng blog TUICOCACH.COM đi tìm hiểu thuật toán tìm kiếm này trong bài viết hôm nay nhé.
Ý tưởng của thuật toán tìm kiếm nhị phân
Giả sử bạn đang có một mảng A bao gồm n phần tử, bạn đang cần tìm kiếm phần tử ở x.
Giải thuật đơn giản nhất cho bài toán tìm kiếm này là sử dụng linear search(tìm kiếm tuyến tính hay gọi là tìm kiếm tuần tự). Tức là bạn sẽ phải đi qua từng phần tử của mảng để đối chiếu với x cần tìm. Thuật toán này trong trường hợp xấu nhất cho độ phức tạp là O(n).
Vậy bạn có đặt ra câu hỏi, có thuật toán nào tìm kiếm nhanh và tối ưu hơn không? Câu trả lời đó là thuật toán tìm kiếm nhị phân(Binary search).
Ý tưởng của thuật toán tìm kiếm nhị phân đó là mỗi lần thực hiện chúng ta sẽ chia mảng ra làm 2 phần, lấy ra phần tử y ở chính giữa và đem phần tử này so sánh với phần tử x cần tìm. Nếu y=x tìm thấy phần tử, ngược lại tiếp tục thực hiện chia mảng đối với mảng con bên trái hoặc mảng con bên phải tùy thuộc vào y<x hay y>x. Thuật toán kết thúc khi tìm thấy phần tử hoặc mảng con không thể chia nhỏ.
Theo như ý tưởng thuật toán ta sẽ lấy ra phần tử y là phần tử chốt và so sánh phần tử chốt này với x cần tìm, mục đích của việc này là kiểm tra xem x nằm ở bên phải hay bên trái mảng so với phần tử chốt là Y. Tức là thuật toán tìm kiếm nhị phân chỉ có thể thực hiện trên mảng đã được sắp xếp(sắp xếp tăng dần hoặc giảm dần), và đây cũng chính là một nhược điểm của thuật toán tìm kiếm này.
- Kiếm tiền Accesstrade, kiếm tiền tại nhà với Accesstrade.vn – Tiếp thị liên kết
- MegaURL – Rút gọn link kiếm tiền có giá cao tại Việt Nam
- Top 4 App kiếm tiền online trên điện thoại tốt nhất 2022
Tiếp tục giả sử mảng A ở trên đã được sắp xếp tăng dần, ta có thể mô tả các bước thực hiện thuật toán như sau:
- Xét đoạn mảng A[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 phần tử arr[mid] = x. Kết luận và thoát chương trình.
- Nếu arr[mid] < x. Chỉ thực hiện tìm kiếm trên đoạn A[mid+1…right].
- Nếu arr[mid] > x. Chỉ thực hiện tìm kiếm trên đoạn A[left…mid-1].
Nếu vẫn chưa thể hình dung, hình ảnh dưới đây mô phỏng quá trình thực hiện của thuật toán tìm kiếm nhị phân và so sánh thuật toán tìm kiếm nhị phân với thuật toán tìm kiếm tuyến tính.
Với thuật toán tìm kiếm nhị phân độ phức tạp cho trường hợp xấu nhất chỉ là O(log(n)).
Minh họa code cho thuật toán tìm kiếm nhị phân
Minh họa thuật toán bằng Đệ quy
#include <stdio.h>
// 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)/2; //vị trí ở giữa
// 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("Khong tim thay phan tu %d trong mang",x);
else
printf("%d xuat hien tai chi so %d", x, result);
return 0;
}
Minh họa thuật toán bằng vòng lặp
Khóa học lập trình C/C++ từ A-Z cho người mới – Giảm giá 40% hôm nay
Khóa học Java cơ bản dành cho người mới bắt đầu- Giảm 40% hôm nay
Khóa học lập trình Android từ cơ bản đến thành thạo – Giảm ngay 40%
#include <stdio.h>
// Hàm tìm kiếm nhị phân
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)/2; //vị trí ở giữa
// 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("Khong tim thay phan tu %d trong mang",x);
else
printf("%d xuat hien tai chi so %d", x, result);
return 0;
}
Cảm ơn bạn đã theo dõi bài viết! Chúc học tốt!
XEM THÊM Thuật toán đếm số lượng chữ số của số nguyên dương n bằng C / C++ Thuật toán sắp xếp nhanh (Quick Sort) Thuật toán sắp xếp trộn (Merge Sort) Một số chương trình xây dựng trên Graphics C/C++ Hướng dẫn cài đặt thư viện Graphics trên IDE Devc++
