Python có sử dụng tìm kiếm nhị phân không?
Hướng dẫn này sẽ tìm hiểu cách chúng ta có thể áp dụng thuật toán tìm kiếm nhị phân bằng Python để tìm vị trí chỉ mục của phần tử trong danh sách đã cho Show Giới thiệuTìm kiếm nhị phân là một thuật toán để tìm một phần tử cụ thể trong danh sách. Giả sử chúng ta có một danh sách gồm hàng nghìn phần tử và chúng ta cần lấy vị trí chỉ mục của một phần tử cụ thể. Chúng ta có thể tìm thấy vị trí chỉ mục của phần tử rất nhanh bằng thuật toán tìm kiếm nhị phân Có nhiều thuật toán tìm kiếm nhưng tìm kiếm nhị phân là phổ biến nhất trong số đó Các phần tử trong danh sách phải được sắp xếp để áp dụng thuật toán tìm kiếm nhị phân. Nếu các phần tử không được sắp xếp thì hãy sắp xếp chúng trước Hãy hiểu khái niệm về tìm kiếm nhị phân Khái niệm về tìm kiếm nhị phânTrong thuật toán tìm kiếm nhị phân, chúng ta có thể tìm vị trí phần tử bằng các phương pháp sau
Kỹ thuật tiếp cận chia để trị được theo sau bởi phương pháp đệ quy. Trong phương thức này, một hàm được gọi lặp đi lặp lại cho đến khi nó tìm thấy một phần tử trong danh sách Một tập hợp các câu lệnh được lặp lại nhiều lần để tìm vị trí chỉ số của phần tử trong phương pháp lặp. Vòng lặp while được sử dụng để hoàn thành nhiệm vụ này Tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính vì chúng ta không cần tìm kiếm từng chỉ mục danh sách. Danh sách phải được sắp xếp để đạt được thuật toán tìm kiếm nhị phân Hãy từng bước triển khai tìm kiếm nhị phân Chúng tôi có một danh sách các phần tử được sắp xếp và chúng tôi đang tìm kiếm vị trí chỉ mục là 45 [12, 24, 32, 39, 45, 50, 54] Vì vậy, chúng tôi đang đặt hai con trỏ trong danh sách của mình. Một con trỏ được sử dụng để biểu thị giá trị nhỏ hơn được gọi là thấp và con trỏ thứ hai được sử dụng để biểu thị giá trị cao nhất được gọi là cao Tiếp theo, chúng ta tính giá trị của phần tử ở giữa trong mảng Bây giờ, chúng ta sẽ so sánh phần tử được tìm kiếm với giá trị chỉ số giữa. Trong trường hợp này, 32 không bằng 45. Vì vậy, chúng ta cần phải so sánh thêm để tìm phần tử Nếu số chúng tôi đang tìm kiếm bằng giữa. Sau đó quay lại giữa nếu không chuyển sang so sánh tiếp theo Số cần tìm lớn hơn số ở giữa, ta so sánh n với phần tử ở giữa của các phần tử vế phải của mid và đặt low là low = mid + 1 Mặt khác, so sánh n với phần tử ở giữa của các phần tử ở bên trái của mid và đặt cao thành cao = mid - 1 Lặp lại cho đến khi tìm thấy số mà chúng tôi đang tìm kiếm Triển khai tìm kiếm nhị phân trong PythonĐầu tiên, chúng tôi thực hiện tìm kiếm nhị phân bằng phương pháp lặp. Chúng tôi sẽ lặp lại một tập hợp các câu lệnh và lặp lại mọi mục trong danh sách. Chúng tôi sẽ tìm giá trị ở giữa cho đến khi quá trình tìm kiếm hoàn tất Hãy hiểu chương trình sau đây của phương pháp lặp Triển khai Pythonđầu ra Element is present at index 4 Giải trình Trong chương trình trên -
Hãy hiểu phương pháp tìm kiếm nhị phân đệ quy Tìm kiếm nhị phân đệ quyPhương pháp đệ quy có thể được sử dụng trong tìm kiếm nhị phân. Trong phần này, chúng ta sẽ định nghĩa một hàm đệ quy tiếp tục gọi chính nó cho đến khi nó thỏa mãn điều kiện Hãy hiểu chương trình trên sử dụng hàm đệ quy Chương trình Pythonđầu ra Element is present at index 2 Giải trình Chương trình trên tương tự như chương trình trước. Chúng tôi đã khai báo một hàm đệ quy và điều kiện cơ bản của nó. Điều kiện là giá trị thấp nhất nhỏ hơn hoặc bằng giá trị cao nhất
Trong phần cuối cùng, chúng tôi đã viết chương trình chính của chúng tôi. Nó giống như chương trình trước, nhưng khác biệt duy nhất là chúng ta đã truyền hai tham số trong hàm binary_search() Điều này là do chúng ta không thể gán các giá trị ban đầu cho mức thấp, cao và trung bình trong hàm đệ quy. Mỗi khi đệ quy được gọi, giá trị sẽ được đặt lại cho các biến đó. Điều đó sẽ cho kết quả sai phức tạpĐộ phức tạp của thuật toán tìm kiếm nhị phân là O(1) cho trường hợp tốt nhất. Điều này xảy ra nếu phần tử mà phần tử chúng ta đang tìm kiếm tìm thấy trong phép so sánh đầu tiên. O(logn) là trường hợp phức tạp nhất và trung bình của tìm kiếm nhị phân. Điều này phụ thuộc vào số lượng tìm kiếm được thực hiện để tìm phần tử mà chúng tôi đang tìm kiếm Sự kết luậnThuật toán tìm kiếm nhị phân là cách hiệu quả và nhanh nhất để tìm kiếm một phần tử trong danh sách. Nó bỏ qua sự so sánh không cần thiết. Như tên cho thấy, tìm kiếm được chia thành hai phần. Nó tập trung vào phía của danh sách, gần với số mà chúng tôi đang tìm kiếm Python có tìm kiếm nhị phân không?Tìm kiếm nhị phân là kỹ thuật dùng để tìm kiếm phần tử trong danh sách đã sắp xếp . Trong bài viết này, chúng ta sẽ xem xét các hàm thư viện để thực hiện Tìm kiếm nhị phân. Tìm sự xuất hiện đầu tiên của một phần tử.
Tìm kiếm nhị phân Python là gì?Tìm kiếm nhị phân là thuật toán tìm kiếm được sử dụng để tìm kiếm một phần tử từ một mảng đã sắp xếp . Nó không thể được sử dụng để tìm kiếm từ một mảng chưa được sắp xếp. Tìm kiếm nhị phân là một thuật toán hiệu quả và tốt hơn tìm kiếm tuyến tính về độ phức tạp của thời gian. Độ phức tạp thời gian của tìm kiếm tuyến tính là O(n).
Python sử dụng cây tìm kiếm nhị phân như thế nào?Triển khai cây B trong Python . Bước 1 - Lớp BSTNode. Việc triển khai của chúng tôi sẽ không sử dụng lớp Cây mà thay vào đó chỉ là lớp Nút. . Bước 2 - Chèn. Chúng ta cần một cách để chèn dữ liệu mới vào cây. . Bước 3 - Nhận tối thiểu và nhận tối đa. . Bước 4 - Xóa. . Bước 5 - Tồn tại. . Bước 6 - Đặt hàng. . Bước 7 - Đặt trước. . Bước 8 - Đặt hàng sau |