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

Trước khi tìm hiểu về tìm kiếm nhị phân, chúng ta hãy cùng tìm hiểu tìm kiếm là gì.

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, tìm và truy xuất 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ó là chia dữ liệu trong danh sách thành hai phần bằng nhau cho đến khi tìm thấy giá trị cần thiết 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 biết đến như một thuật toán tìm kiếm nhị phân. 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 xác định 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ì thuật toán tìm kiếm sẽ phân tích các giá trị lớn hơn phần tử ở giữa để so sánh và đối khớp.
• Trong trường hợp giá trị khóa lớn hơn phần tử ở giữa, thì quá trình tìm kiếm sẽ phân tích các giá trị nhỏ hơn phần tử ở giữa để so sánh và đối khớp.

Thuật toán tìm kiếm nhị phân (Mã giả)

Thuật toán tìm kiếm nhị phân có thể được viết dưới dạng một quy trình lặp ngắn. Nó giữ hai con trỏ, thấp và cao, và thu hẹp phạm vi cho đến khi tìm thấy mục tiêu hoặc phạm vi trở nên trống.

binarySearch(array, target)
    low = 0
    high = length(array) - 1
    while low <= high
        mid = (low + high) / 2      // floor value
        if array[mid] == target
            return mid
        else if array[mid] < target
            low = mid + 1
        else
            high = mid - 1
    return -1              // target not found

Thủ tục này trả về chỉ số của mục tiêu khi thành công và -1 khi giá trị không tồn tại. Vì phạm vi giảm đi một nửa sau mỗi lần lặp, vòng lặp chạy tối đa log₂(n) lần.

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:

1. Bạn có một mảng gồm 10 chữ số và cần tìm phần tử 59.
2. Tất cả các phần tử được đánh số từ 0 đến 9. Bây giờ, vị trí giữa của mảng được tính toán. Để làm điều đó, bạn lấy giá trị đầu tiên bên trái và bên phải của chỉ số rồi chia cho 2. Kết quả là 4.5, nhưng chúng ta lấy giá trị làm tròn xuống. Do đó, vị trí giữa là 4.
3. Thuật toán loại bỏ tất cả các phần tử từ giữa (4) đến 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ử.
4. Bây giờ, 59 lớn hơn 45 và nhỏ hơn 63. Số ở giữa là 7. Do đó, giá trị chỉ số bên phải trở thành số ở giữa trừ đi 1, bằng 6, và giá trị chỉ số bên trái vẫn giữ nguyên như trước, là 5.
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.
6. 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 hoạt động của thuật toán tìm kiếm nhị phân.

1. 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.
2. Trung bình cộng của giới hạn dưới và giới hạn trên là (l + r) / 2 = 4. Giá trị cần tìm lớn hơn giá trị trung bình, tức là 4.
3. Các giá trị trong mảng nhỏ hơn giá trị trung bình sẽ bị loại bỏ khỏi quá trình tìm kiếm, và các giá trị lớn hơn giá trị trung bình là 4 sẽ được tìm kiếm.
4. Đâ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:

• Thuật toán 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 thứ tự thay vì sử dụng phép so sánh bằng nhau, vốn chậm hơn và hầu hết không chính xác.
• Sau mỗi chu kỳ tìm kiếm, thuật toán sẽ chia kích thước của mảng thành hai phần bằng nhau; do đó, trong lần lặp tiếp theo, nó sẽ chỉ hoạt động trên phần mảng còn lại.

Hãy cùng tìm hiểu bài 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ìm kiếm nhị phân so với tìm kiếm tuyến tính

Tìm kiếm nhị phân và tìm kiếm tuyến tính là hai phương pháp phổ biến nhất để tìm một giá trị trong một tập hợp. Bảng dưới đây nêu bật sự khác biệt giữa chúng:

Tóm lại, tìm kiếm nhị phân nhanh hơn nhiều trên các tập dữ liệu lớn đã được sắp xếp, trong khi tìm kiếm tuyến tính đơn giản hơn và là lựa chọn duy nhất khi dữ liệu chưa được sắp xếp.

Câu Hỏi Thường Gặp