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
Giới thiệu
Tì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ân
Trong 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
- Phương pháp đệ quy
- Phương pháp lặp
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 -
- Chúng tôi đã tạo một hàm có tên là hàm binary_search[] nhận hai đối số - một danh sách để sắp xếp và một số để tìm kiếm
- Chúng tôi đã khai báo hai biến để lưu trữ các giá trị thấp nhất và cao nhất trong danh sách. Mức thấp được gán giá trị ban đầu là 0, mức cao là len[list1] - 1 và mức trung bình là 0
- Tiếp theo ta đã khai báo vòng lặp while với điều kiện số thấp nhất bằng và nhỏ hơn số cao nhất Vòng lặp while sẽ lặp nếu chưa tìm được số
- Trong vòng lặp while, chúng tôi tìm giá trị trung bình và so sánh giá trị chỉ mục với số chúng tôi đang tìm kiếm
- Nếu giá trị của chỉ số giữa nhỏ hơn n, chúng tôi tăng giá trị giữa lên 1 và gán nó cho Tìm kiếm di chuyển sang bên trái
- Nếu không, hãy giảm giá trị trung bình và gán nó cho giá trị cao. Tìm kiếm di chuyển sang phía bên phải
- Nếu n bằng giá trị giữa thì trả về mid
- Điều này sẽ xảy ra cho đến khi mức thấp bằng và nhỏ hơn mức cao
- Nếu chúng ta đến cuối hàm, thì phần tử không có trong danh sách. Chúng tôi trả về -1 cho chức năng gọi
Hãy hiểu phương pháp tìm kiếm nhị phân đệ quy
Tìm kiếm nhị phân đệ quy
Phươ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
- Chúng tôi tính toán số ở giữa như trong chương trình cuối cùng
- Chúng tôi đã sử dụng câu lệnh if để tiến hành tìm kiếm nhị phân
- Nếu giá trị ở giữa bằng với số mà chúng tôi đang tìm kiếm, giá trị ở giữa sẽ được trả về
- Nếu giá trị ở giữa nhỏ hơn giá trị, thì chúng ta sẽ xem lại hàm đệ quy binary_search[] và tăng giá trị ở giữa lên một và gán cho giá trị thấp
- Nếu giá trị ở giữa lớn hơn giá trị mà chúng ta đang tìm kiếm thì hàm đệ quy của chúng ta binary_search[] một lần nữa và giảm giá trị ở giữa xuống một và gán nó ở mức thấp
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ận
Thuậ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