Trong bài viết ngày hôm nay chúng tôi sẽ hướng dẫn bạn cách tìm kiếm nhị phân trong c++. Đây cũng chính là thuật toán phổ biến để tìm kiếm một phần tử trong một mảng đã sắp xếp. Cùng chúng tôi theo dõi ví dụ dưới đây để hiểu rõ hơn nhé!
Cách tìm kiếm nhị phân trong c++
Ví dụ: Cho một danh sách arr[] đã được sắp xếp bao gồm có n phần từ à viết một hàm đưa ra vị trí của phần tử x trong mảng.
Ta có:
Input : arr[] = {15, 20, 25, 30, 31, 44, 66}
x = 25;
Output : 2
Để giải quyết đề toán này chúng ta sẽ sử dụng thuật toán nhị phân được giới thiệu ngay bên dưới đây nhé!
Cách tìm kiếm số nhị phân
Thuật toán tìm kiếm nhị phân trong c++ hay còn có tên gọi khác là tìm kiếm một nửa là thuật toán tiếp kiếm được sử dụng trong rất nhiều phép tìm kiếm vị trí của một phân tử đã sắp xếp trong một mảng.
Thuật toán tìm kiếm nhị phân tiến hành thực hiện tìm kiếm một mảng đã được sắp xếp bằng cách liên tục chia khoảng cách tìm kiếm thành một nửa. Sau đó bắt đầu với khoảng cách từ phần tử đầu mảng tơi cuối mảng. Ta có nếu như 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 cho đến giữa mảng và ngược lại. Cứ như vậy tiếp tục chia phạm vi thành các nửa cho đến khi tìm thấy hay đã duyệt hết.
Trong thuật toán tìm kiếm nhị phân sẽ toe ra tối ưu hơn so với tìm kiếm tuyến tính ở các mảng có độ dài lớn và được sắp xếp, ngược lại tìm kiếm tuyến tính sẽ tỏ ra hiệu quả hơn khi mà triển khai các mảng nhỏ và chưa được sắp xếp.
Ý tưởng triển khai thuật toán
thuật toán tìm kiếm số nhị phân là một trong những thuật toán thông dụng và chỉ dùng được với một mảng đã sắp xếp. Do đó để triển khai thuật toán này cần chắc chắn rằng mảng đã được sắp xếp và sau đây chúng tôi sẽ đưa ra ý tưởng triển khai thuật toán.
- Đầu tiên tiến hành xét một đoạn trong mảng arr[left…right]. Lúc này giá trị của left và right sẽ lần lượt là và số phần tử của mảng – 1.
- Tiếp đến so sánh x với phần tử nằm ở vị trí chính giữa của mảng (mid = (left + right) /2). Nếu như x mà bằng arr[mid] thì trả về vị trí và thoát vòng lặp.
- Nếu x < arr[mid] thì điều này chứng tỏ x sẽ nằm ở phía bên trái tức là từ arr[left….mid-1].
- Nếu x > arr[mid] thì chứng tỏ rằng x sẽ nằm ở phía bên phải mid hay tức là ở khoảng arr[mid+1…right].
- Tiếp theo thực hiện chia đôi các khoảng tìm kiếm cho tới khi nào thấy được vị trí của x trong mảng hoặc khi đã duyệt được hết mảng.
Người ta đã chứng minh rằng độ phức tạp của các thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), và trong trường hợp xấu nhất thì O(log2n). Tuy vậy ta không được quên rằng trước khi sử dụng tìm kiếm nhị phân thì dãy khóa phải được sắp xếp rôi và tức là thời gian chi phí cho việc sắp xếp cũng cần phải tính đến.
Triển khai thuật toán
Cách tìm kiếm nhị phân trong c++
Sau đây là các bước triển khai thuật toán tìm số nhị phân, các bước đều được tiến hành như ở thông tin bên dưới bài viết.
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 <bits/stdc++.h> using namespace std;
//Hàm tìm kiếm nhị phân int binarySearch(int arr[], int left, int right, int x) { int middle;
while(left <= right) { // Lấy 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ì // chắc chắn nó nằm bên phải. // Ở đây chúng ta chỉ định left là 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 như không tìm được giá 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 được xác định là vị trí cuối cùng trong mảng int result = binarySearch hay có (arr, 0, n-1, x);
cout << result; } |
Khi bạn khởi chạy chương trình sẽ nhận được kết quả là vị trí 25 của mảng.
| 1 | Output : 2 |
Trên đây chính là phần dưới thiệu cũng như triển khai của thuật toán tìm kiếm nhị phân trong c++. Đây cũng chính là thuật toán được sử dụng rất nhiều và rất hữu ích cho quá trình giải các bài toán tìm kiếm và mong là các thông tin này hữu ích cho các bạn.