Trước khi tìm hiểu Tìm kiếm nhị phân, chúng ta hãy tìm hiểu:
Tìm kiếm là gì?
Tìm kiếm là một tiện ích cho phép người dùng tìm tài liệu, tệp, phương tiện hoặc bất kỳ loại dữ liệu nào khác được lưu giữ bên trong cơ sở dữ liệu. Tìm kiếm hoạt động trên nguyên tắc đơn giản là khớp các tiêu chí với các bản ghi và hiển thị nó cho người dùng. Bằng cách này, chức năng tìm kiếm cơ bản nhất hoạt động.
Tìm kiếm nhị phân là gì?
Tìm kiếm nhị phân là một loại thuật toán tìm kiếm nâng cao để tìm và lấy dữ liệu từ một danh sách các mục đã được sắp xếp. Nguyên tắc hoạt động cốt lõi của nó liên quan đến việc chia dữ liệu trong danh sách thành một nửa cho đến khi giá trị yêu cầu được định vị và hiển thị cho người dùng trong kết quả tìm kiếm. Tìm kiếm nhị phân thường được gọi là tìm kiếm nửa khoảng hoặc tìm kiếm theo lôgarit .
Trong hướng dẫn thuật toán này, bạn sẽ học:
- Tìm kiếm là gì?
- Tìm kiếm nhị phân là gì?
- Tìm kiếm nhị phân hoạt động như thế nào?
- Ví dụ về tìm kiếm nhị phân
- Tại sao chúng ta cần tìm kiếm nhị phân?
Tìm kiếm nhị phân hoạt động như thế nào?
Tìm kiếm nhị phân hoạt động theo cách sau:
- Quá trình tìm kiếm bắt đầu bằng cách định vị phần tử ở giữa của mảng dữ liệu đã được sắp xếp
- Sau đó, giá trị khóa được so sánh với phần tử
- Nếu giá trị khóa nhỏ hơn phần tử giữa, thì tìm kiếm sẽ phân tích các giá trị phía trên cho phần tử giữa để so sánh và đối sánh
- Trong trường hợp giá trị khóa lớn hơn phần tử giữa thì tìm kiếm sẽ phân tích các giá trị thấp hơn cho phần tử giữa để so sánh và đối sánh
Ví dụ về tìm kiếm nhị phân
Chúng ta hãy xem ví dụ về từ điển. Nếu cần tìm một từ nào đó, không ai đi tuần tự từng từ mà đặt ngẫu nhiên những từ gần nhất để tìm từ cần thiết.
Hình ảnh trên minh họa những điều sau:
- Bạn có một mảng gồm 10 chữ số và phần tử 59 cần được tìm thấy.
- Tất cả các phần tử được đánh dấu bằng chỉ số từ 0 - 9. Bây giờ, phần giữa của mảng được tính toán. Để làm như vậy, bạn lấy các giá trị ngoài cùng bên trái và bên phải của chỉ số và chia chúng cho 2. Kết quả là 4,5, nhưng chúng tôi lấy giá trị sàn. Do đó giữa là 4.
- Thuật toán loại bỏ tất cả các phần tử từ giữa (4) xuống giới hạn thấp nhất vì 59 lớn hơn 24 và bây giờ mảng chỉ còn lại 5 phần tử.
- Bây giờ, 59 lớn hơn 45 và nhỏ hơn 63. Giữa là 7. Do đó, giá trị chỉ số bên phải trở thành giữa - 1, bằng 6 và giá trị chỉ số bên trái vẫn như trước, là 5.
- Tại thời điểm này, bạn biết rằng 59 đến sau 45. Do đó, chỉ số bên trái, là 5, cũng trở thành giữa.
- Các lần lặp này tiếp tục cho đến khi mảng được giảm xuống chỉ còn một phần tử hoặc mục cần tìm trở thành phần giữa của mảng.
Ví dụ 2
Hãy xem ví dụ sau để hiểu tìm kiếm nhị phân hoạt động
- Bạn có một mảng các giá trị được sắp xếp từ 2 đến 20 và cần xác định vị trí 18.
- Giá trị trung bình của giới hạn dưới và giới hạn trên là (l + r) / 2 = 4. Giá trị đang được tìm kiếm lớn hơn giá trị giữa là 4.
- Các giá trị mảng nhỏ hơn giá trị giữa sẽ bị loại bỏ khỏi tìm kiếm và các giá trị lớn hơn giá trị giữa 4 được tìm kiếm.
- Đây là một quá trình phân chia lặp đi lặp lại cho đến khi tìm thấy mục thực sự cần tìm.
Tại sao chúng ta cần tìm kiếm nhị phân?
Những lý do sau đây làm cho tìm kiếm nhị phân trở thành một lựa chọn tốt hơn để được sử dụng làm thuật toán tìm kiếm:
- Tìm kiếm nhị phân hoạt động hiệu quả trên dữ liệu được sắp xếp bất kể kích thước của dữ liệu
- Thay vì thực hiện tìm kiếm bằng cách xem qua dữ liệu theo một chuỗi, thuật toán nhị phân truy cập ngẫu nhiên vào dữ liệu để tìm phần tử cần thiết. Điều này làm cho các chu kỳ tìm kiếm ngắn hơn và chính xác hơn.
- Tìm kiếm nhị phân thực hiện so sánh dữ liệu được sắp xếp dựa trên nguyên tắc sắp xếp hơn là sử dụng so sánh bình đẳng, chậm hơn và chủ yếu là không chính xác.
- Sau mỗi chu kỳ tìm kiếm, thuật toán chia kích thước của mảng thành một nửa, do đó trong lần lặp tiếp theo nó sẽ chỉ hoạt động trong nửa còn lại của mảng
Tóm lược
- Tìm kiếm là một tiện ích cho phép người dùng tìm kiếm tài liệu, tệp và các loại dữ liệu khác. Tìm kiếm nhị phân là một loại thuật toán tìm kiếm nâng cao để tìm và lấy dữ liệu từ một danh sách các mục đã được sắp xếp.
- Tìm kiếm nhị phân thường được gọi là tìm kiếm nửa khoảng hoặc tìm kiếm theo lôgarit
- Nó hoạt động bằng cách chia mảng thành một nửa trên mỗi lần lặp dưới phần tử bắt buộc được tìm thấy.
- Thuật toán nhị phân lấy giữa mảng bằng cách chia tổng giá trị chỉ số bên trái và ngoài cùng bên phải cho 2. Bây giờ, thuật toán giảm giới hạn dưới hoặc giới hạn trên của các phần tử từ giữa mảng, tùy thuộc vào phần tử được tìm thấy .
- Thuật toán truy cập ngẫu nhiên dữ liệu để tìm phần tử cần thiết. Điều này làm cho các chu kỳ tìm kiếm ngắn hơn và chính xác hơn.
- Tìm kiếm nhị phân thực hiện so sánh dữ liệu được sắp xếp dựa trên nguyên tắc sắp xếp thứ tự hơn là sử dụng so sánh bình đẳng chậm và không chính xác.
- Tìm kiếm nhị phân không phù hợp với dữ liệu chưa được sắp xếp.