Thuật toán tìm kiếm nhị phân với EXAMPLE

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ữ trong cơ sở dữ liệu. Tìm kiếm hoạt động theo nguyên tắc đơn giản là khớp tiêu chí với 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 sẽ 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 giúp tìm và lấy dữ liệu 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 đôi dữ liệu trong danh sách cho đến khi giá trị được yêu cầu được tìm thấy 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 thời gian hoặc một tìm kiếm logarit.

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 việc đị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ị cao hơn đến phần tử ở giữa để so sánh và khớp
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à khớp

Ví dụ tìm kiếm nhị phân

Hãy xem ví dụ về một từ điển. Nếu bạn cần tìm một từ nào đó, không ai duyệt qua từng từ theo trình tự mà sẽ ngẫu nhiên tìm những từ gần nhất để tìm từ cần tìm.

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à cần tìm phần tử 59.
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 giá trị ngoài cùng bên trái và bên phải của chỉ mục rồi chia cho 2. Kết quả là 4.5 nhưng chúng tôi lấy giá trị sàn. Do đó số ở giữa là 4.
Thuật toán giảm 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. Số ở giữa là 7. Do đó, giá trị chỉ mục bên phải trở thành ở giữa – 1, bằng 6 và giá trị chỉ mục bên trái vẫn giữ nguyên như trước, là 5.
Tại thời điểm này, bạn biết rằng 59 đứng sau 45. Do đó, chỉ số bên trái là 5 cũng trở thành trung bình.
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 tìm thấy trở thành phần giữa của mảng.

Ví dụ 2

Hãy xem ví dụ sau để hiểu cách 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 khỏi tìm kiếm và các giá trị lớn hơn giá trị giữa 4 sẽ được tìm kiếm.
Đây là 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 khiến tìm kiếm nhị phân trở thành lựa chọn tốt hơn để 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 duyệt qua dữ liệu theo trình tự, thuật toán nhị phâ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 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 so với sử dụng so sánh bằng nhau, phương pháp này chậm hơn và hầu như 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 đó ở lần lặp tiếp theo, nó sẽ chỉ hoạt động ở nửa còn lại của mảng.

Tìm hiểu hướng dẫn tiếp theo của chúng tôi về Tìm kiếm tuyến tính: Python, C++ Ví dụ

Tổng kết

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 giúp tìm và lấy dữ liệu 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 logarit
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 theo phần tử bắt buộc được tìm thấy.
thuật toán nhị phân lấy phần giữa của mảng bằng cách chia tổng giá trị chỉ số ngoài cùng bên trái và bên phải cho 2. Bây giờ, thuật toán loại bỏ giới hạn dưới hoặc giới hạn trên của các phần tử khỏi 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 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 thay vì sử dụng các so sánh đẳng thức 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.