Tìm kiếm nhị phân [Binary Search] là một thuật toán tìm kiếm nhanh với độ phức tạp trong thời gian chạy là Ο[log n]. Thuật toán tìm kiếm này hoạt động theo nguyên tắc chia để trị. Để thuật toán này có thể hoạt động bình thường, việc thu thập dữ liệu phải ở dạng đã được sắp xếp.
Binary Search tìm kiếm một mục cụ thể bằng cách so sánh mục ở giữa nhất của bộ sưu tập. Nếu khớp xảy ra, thì chỉ mục của mục được trả về. Nếu mục ở giữa lớn hơn mục, thì mục đó được tìm kiếm trong mảng con bên trái của mục ở giữa. Mặt khác, mục được tìm kiếm sẽ nằm trong mảng phụ ở bên phải của mục ở giữa. Quá trình này cũng tiếp tục trên mảng con cho đến khi kích thước của mảng con giảm xuống bằng không.
Tìm kiếm nhị phân hoạt động như thế nào?
Để tìm kiếm nhị phân hoạt động, bắt buộc phải sắp xếp mảng mục tiêu. Chúng ta sẽ tìm hiểu quá trình tìm kiếm nhị phân với một ví dụ bằng hình ảnh. Sau đây là mảng đã sắp xếp của chúng ta và giả sử rằng chúng ta cần tìm kiếm vị trí của giá trị 31 bằng cách sử dụng tìm kiếm nhị phân.
Đầu tiên, chúng ta sẽ xác định một nửa mảng bằng cách sử dụng công thức này:
mid = low + [high - low] / 2
Đây là 0 + [9 – 0 ] / 2 = 4 [giá trị nguyên là 4,5]. Vì vậy, 4 là giữa của mảng.
Bây giờ, chúng ta so sánh giá trị được lưu trữ tại vị trí 4, với giá trị đang được tìm kiếm, tức là 31. Chúng ta thấy rằng giá trị tại vị trí 4 là 27, giá trị này không khớp. Vì giá trị lớn hơn 27 và chúng ta có một mảng được sắp xếp, nên chúng ta cũng biết rằng giá trị đích phải nằm ở phần trên của mảng.
Chúng ta thay đổi mức thấp thành mức trung bình + 1 và tìm lại giá trị mức trung bình mới.
low = mid + 1
mid = low + [high - low] / 2
Trung bình mới của chúng ta bây giờ là 7. Ta so sánh giá trị được lưu trữ tại vị trí 7 với giá trị mục tiêu 31.
Giá trị được lưu trữ tại vị trí 7 không khớp, thay vào đó, nó lớn hơn mục tiêu tìm kiếm. Vì vậy, giá trị phải ở phần dưới từ vị trí này.
Do đó, ta tính toán lại giữa. Lần này là 5.
So sánh giá trị được lưu trữ tại vị trí 5 với giá trị mục tiêu. Ta thấy trùng khớp.
Chúng ta kết luận rằng giá trị mục tiêu 31 được lưu trữ tại vị trí 5.
Tìm kiếm nhị phân giảm một nửa các mục có thể tìm kiếm và do đó làm giảm số lần so sánh được thực hiện với số lượng rất ít.
Pseudocode
Pseudocode của thuật toán binary search trông sẽ như thế này:
`Procedure binary_search A ← sorted array n ← size of array x ← value to be searched Set lowerBound = 1 Set upperBound = n while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + [ upperBound - lowerBound ] / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
Nếu bạn muốn hiểu sâu hơn về Binary Search, đăng ký ngay lớp học thuật toán FSE Big Tech – học trực tiếp từ giảng viên hiện đang làm việc tại các công ty hàng đầu như Google, Amazon, TikTok, Booking, Grab!
Thuật toán tìm kiếm nhị phân [Binary Search] được sử dụng để tìm kiếm một giá trị trong một danh sách đã sắp xếp. Thuật toán này cài đặt theo phương pháp đệ quy sẽ giảm số phép toán so sánh và làm cho thuật toán chạy nhanh hơn. Trong trường hợp tệ nhất thì độ phức tạp của thuật toán sẽ là O[log n], với n là số phần tử của mảng.
Cách thực hiện
Ví dụ chúng ta có một mảng gồm các phần tử 1 2 4 6 7 8 9 10. Bây giờ chúng ta nhập vào một số nào đó. Ví dụ số cần tìm x=9, thuật toán sẽ làm như sau:
- Lấy giá trị chính giữa của dãy số y so sánh với x, nếu x nhỏ hơn thì tìm trong danh sách từ phần tử đầu tiên đến trước phần tử y, ngược lại thì tìm từ phần tử ngay sau y đến phần tử cuối cùng.
- Lặp lại bước trên cho đến khi gặp được x.
Đã tìm được x ở vị trí số 7.
Yêu cầu
Viết chương trình để cài đặt thuật toán tìm kiếm nhị phân [Binary Search] để tìm kiếm giá trị trong một mảng đã sắp xếp.
Phân tích và tìm cách giải
- Đầu vào: Một mảng số đã sắp xếp, giá trị x cần tìm.
- Đầu ra: In ra vị trí tìm được trong mảng
- Phân tích:
- – Hàm sử tìm kiếm BinarySearch[a[], start, end]
- – Tính k=[start + end]/2
- – Bước cơ sở:
- If a[k] = x -> return k //tìm thấy
- If k=end -> return -1 //không tìm thấy
- Bước đệ qui:
- If a[k]