Thư viện tiêu chuẩn tìm kiếm nhị phân python
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 Phần 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 cạnh của danh sách, gần với số mà chúng tôi đang tìm kiếm Có tìm kiếm nhị phân tích hợp trong Python không?Khoa học dữ liệu thực tế sử dụng Python
. Kỹ thuật tìm kiếm nhị phân được sử dụng để tìm các phần tử trong danh sách đã sắp xếp. Bisect là một chức năng thư viện. The bisect is used for binary search. The binary search technique is used to find elements in sorted list. The bisect is one library function.
Thư viện bisect trong Python là gì?Mã nguồn. Lib/chia đôi. py. Mô-đun này cung cấp hỗ trợ để duy trì danh sách theo thứ tự được sắp xếp mà không phải sắp xếp danh sách sau mỗi lần chèn .
Hai chức năng tìm kiếm nhị phân Python có sẵn là gì?Nếu danh sách không được sắp xếp, thì trước tiên thuật toán sẽ sắp xếp các phần tử bằng thuật toán sắp xếp, sau đó chạy chức năng tìm kiếm nhị phân để tìm đầu ra mong muốn. Có hai phương pháp mà chúng ta có thể chạy thuật toán tìm kiếm nhị phân i. e, phương pháp lặp hoặc phương pháp đệ quy
Tìm kiếm chia đôi trong Python là gì?Tìm kiếm chia đôi/nhị phân là gì? . Điểm nhanh về tìm kiếm nhị phân. a search algorithm that finds the position/index of an element within a sorted search list. Quick points about binary search. |