Làm thế nào để bạn tìm thấy điểm giữa của một tìm kiếm nhị phân?

2024 Tác giả: Lynn Donovan | [email protected]. Sửa đổi lần cuối: 2023-12-15 23:55

Đưa ra một mảng đã sắp xếp, chúng tôi tìm thấy ở giữa phần tử -most và kiểm tra phần tử bằng khóa. Nếu ở giữa phần tử -most bằng với khóa, chúng tôi đã tìm thấy khóa. Nếu ở giữa phần tử -most lớn hơn khóa, chúng tôi Tìm kiếm ở nửa bên trái của ở giữa -phần tử cuối cùng, khác chúng tôi Tìm kiếm ở nửa bên phải.

Tương tự như vậy, mọi người hỏi, làm thế nào để bạn tìm thấy một tìm kiếm nhị phân?

Tìm kiếm nhị phân : Tìm kiếm một mảng được sắp xếp bằng cách chia liên tục Tìm kiếm khoảng thời gian một nửa. Bắt đầu bằng một khoảng bao gồm toàn bộ mảng. Nếu giá trị của Tìm kiếm khóa nhỏ hơn mục ở giữa khoảng, thu hẹp khoảng xuống nửa dưới. Nếu không, hãy thu hẹp nó ở nửa trên.

Tương tự như vậy, O lớn của tìm kiếm nhị phân là gì? Tìm kiếm nhị phân trên thực tế là một Tìm kiếm hoạt động trên một BST cân bằng ( Tìm kiếm nhị phân cây). Như một Tìm kiếm có thời gian phức tạp O (log n). Hãy xem, mảng đã sắp xếp của bạn có thể được xem như là phần đầu tiên theo chiều sâu Tìm kiếm sự nối tiếp theo thứ tự của một BST cân bằng. Đó là, thực hiện một cách đệ quy như sau (bắt đầu với gốc):

Cũng biết, 7 bước của một tìm kiếm nhị phân là gì?

Thuật toán tìm kiếm nhị phân

• Bước 1 - Đọc phần tử tìm kiếm từ người dùng.
• Bước 2 - Tìm phần tử ở giữa trong danh sách đã sắp xếp.
• Bước 3 - So sánh phần tử tìm kiếm với phần tử ở giữa trong danh sách đã sắp xếp.
• Bước 4 - Nếu cả hai đều phù hợp, thì hiển thị "Đã tìm thấy phần tử !!!" và chấm dứt chức năng.

Tìm kiếm nhị phân hoạt động như thế nào?

Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm một mục từ danh sách các mục đã được sắp xếp. Nó làm bằng cách liên tục chia đôi phần của danh sách có thể chứa mục, cho đến khi bạn thu hẹp các vị trí có thể chỉ còn một.